本文共 1352 字，大约阅读时间需要 4 分钟。
n个人，已知每个人体重，独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？
（2.1）如果最优解中，最重的人单独占用一条船，则可以把最轻的人也放上去，这样最优解用的船数不增加。如果最轻的人占用一条船，同样我们可以把最重的人放上去，最优解船数不增。
（2.2） 如果最优解中最重的人x和x’占用一只船(x, x’)，而最轻的人y和y’占用一只船(y, y’)
我们换成(x, y) (x’,y’)
(x, y)显然没超过船的承重——因为我们假设就是如此。关键看(x’, y’)。
x’ + y’<= x’ + x 因为(x’, x)没超重，所以(x’,y’)也合法。所以换一下，最优解船数也不增。这样我们就证明了如果可能把最重的人和最轻的人放在一条船上，不会影响最优解。
第一行包含两个正整数n (0<=10000)和m (0 <=2000000000)，表示人数和独木舟的承重。接下来n行，每行一个正整数，表示每个人的体重。体重不超过1000000000，并且每个人的体重不超过m。
一行一个整数表示最少需要的独木舟数。
3 6123
#include#include #define MAX 10000+5using namespace std;int w[MAX];int n, max_w;bool cmp(int a, int b){ return a > b;}int main() { scanf("%d%d",&n,&max_w); for(int i = 0; i < n; ++i){ scanf("%d",&w[i]); } sort(w,w+n,cmp);//体重按照从大到小排序 int ans = 0; for(int i = 0,j = n-1; i < n; ++i){ if(i > j) break; if(i != j && w[i]+w[j] < max_w)//i == j时候不能相加了 --j;//不超载 就把末尾的带上 ++ans;//无论体重和是否超载都要加1 } printf("%d",ans); return 0; }
转载地址：http://jhimi.baihongyu.com/