独木舟上的旅行

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

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，船数量不变，还是没有比以前更优。还是回到前面的想法做就好了。

 

#include<cstdio>
#include<algorithm>
using namespace std;
int a[30010];
int main()
{
    int n,v,ans=0;
    scanf("%d %d",&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int l=1,r=n;
    while(l<=r)
    {
        if(a[l]+a[r]<=v)
        {
            l++;
            r--;
            ans++;
        }
        else
        {
            r--;
            ans++;
        }
    }
    printf("%d
",ans);
    return 0;
}