乘船问题:
要点什么的看白书,解释的已经很详细了。从这道题我们可以证明贪心法不会丢失最优解,因此可以通过贪心得到最优解。
题目: 点击打开链接
#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;
}