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