独木舟上的旅行

我们计划搞一次独木舟旅游活动。独木舟可以在港口租到，并且它们之间是没有区别的。一条独木舟上最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们想要尽可能的减少我们在这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟的条数。
任务：
请写一个程序：读入独木舟的最大承载量，旅客的数目和每位旅客的重量；
根据给出的规则，计算要安置所有旅客所必须最少的独木舟的条数.

Input

第一行包括一个整数w，80  w  200，为一条独木舟的最大承载量。
文件的第二行为一个整数n，1  n  30000，表示旅客的数目。
以下的n行中每行包含一个[5..w]中的整数，表示所对应旅客的重量。

Output

输出一个整数——所需要的最少独木舟的数目。

Sample Input

100
9
90
20
20
30
50
60
70
80
90

Sample Output

6

sol：贪心入门题，按旅客重量从小到大排成一排，然后一前一后搭配乘船。如排序后旅客重量为a,b,c,d,e,f,我们用一个l，一个r指针指向一前一后旅客。如果l与r所指向的旅客重量和大于limit，只能载一个旅客，r--，ans++，如果l与r所指向的旅客重量和小于limit，则两个旅客同时乘船，r--，l++，ans++。

即该题正向考虑，l如果能带走r，则带走之，为后面的船减轻负担，否则r只能一人坐一条船，因为l已经是最小的了。如果我们反向考虑，能否找到更优的情况。

如四人排序后依次为a，b，c，d，若d可以带走a，我们试试看d能否带走更大的b，其实没必要。因为b+d<limit,则b+c<limit,a+d<limit，船数量不变，还是没有比以前更优。还是回到前面的想法做就好了。

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[30010];
 5 int main()
 6 {
 7     int n,v,ans=0;
 8     scanf("%d %d",&v,&n);
 9     for(int i=1;i<=n;i++)
10         scanf("%d",&a[i]);
11     sort(a+1,a+1+n);
12     int l=1,r=n;
13     while(l<=r)
14     {
15         if(a[l]+a[r]<=v)
16         {
17             l++;
18             r--;
19             ans++;
20         }
21         else
22         {
23             r--;
24             ans++;
25         }
26     }
27     printf("%d\n",ans);
28     return 0;
29 }