当前位置: 代码迷 >> 综合 >> 贪心法经典问题总结
  详细解决方案

贪心法经典问题总结

热度:17   发布时间:2024-01-16 13:47:27.0

乘船问题:

要点什么的看白书,解释的已经很详细了。从这道题我们可以证明贪心法不会丢失最优解,因此可以通过贪心得到最优解。
题目: 点击打开链接
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;int main()
{int t,w,n,i,j;int a[305];scanf("%d", &t);while (t--){scanf("%d%d", &w, &n);for (i = 0; i < n; i++)scanf("%d", &a[i]);sort(a, a + n);int num = 0;i = 0; j = n-1;while (i <= j)//注意这里i=j也行,就是一个人一条船{while (a[i] + a[j]>w){j--;num++;		//如果连当前最轻的匹配不了,只能一个人一条船了}num++;i++; j--;		//匹配上了,i++并j--}printf("%d\n", num);}return 0;
}

选择不相交区间:

  相关解决方案