独木舟
题目信息
旅行社计划组织一个独木舟旅行，租用的独木舟都是一样的，最多乘两人，而且载重有一个限度。 现在要节约费用，所以要尽可能地租用最少的舟。 本题的任务是读入独木舟的载重量，参加旅行的人数以及每个人的体重，计算出所需要的独木舟数目。
输入格式
第 1 行是 w（80≤w≤200），表示每条独木舟最大的载重量。 第 2 行是正整数 n（1≤n≤30000），表示参加旅行的人数。 接下来的 n 行，每行是一个正整数 ti（5≤ti≤w），表示每个人的重量。
输出格式
输出一行一个数，表示最少的独木舟数目。
分析
因为要节约费用，所以要尽可能地租用最少的船，我们需要使得船的浪费是最少的。一艘船乘坐的人数最大为2，但是船的载重量是有特定要求的，所以在这样的情况下，会有以下的思考：
- 如果n个人中，最轻的人都大于船的载重量，那么就无法坐船了（当然，这一点并不用多思考，因为题目中数据范围告诉我们不可能发生这样的情况）
此时我们想要使得浪费最少，那么应该是两个人搭配进行乘船，也就是我们需要找到两个人的体重和小于等于船的载重量。
这两个人怎么找？
随便选的话，这样考虑起来太过于复杂。如果进行枚举，人数又很多，会超时。所以我们思考，怎么取浪费会最少。
想要让浪费最少，那么我们就需要看一下，在最轻的人乘船时，最重的能不能跟着最轻的坐在一条船上，如果可以，那么此时让最轻的和最重的坐在一条船上。
i 代表最轻的人的编号
j 代表最重的人的编号
if(a[i]+a[j]<=船的载重量){
此时 i 和 j 同时上船，然后考虑下一组
}
else{
这里表示最轻的和最重的搭配在一起的时候无法上船，所以此时我们只能让最重的单独一条船，让后让最轻的和第二重的进行搭配。
}贪心策略： 按照人的体重进行升序排序，然后挑选出最轻的和最重的一条船，如果此时体重大于载重量，则最重的单独一条船。反之，如果两人体重不大于载重量，则这两个人搭配在一起租一条船。 后面持续下去...直到所有人安排完
#include<bits/stdc++.h>
using namespace std;
/*
解析：要尽可能租用最少的，而且每条船最多乘两人
如果最小的加上最大的都超过载重量，那么最大的只能单独一条船。
那么此时再用最小的加上第二大的
*/
int a[30005];
int main()
{
int w,n,i,cnt=0;
int start,end;
cin>>w>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
//升序排序
sort(a+1,a+n+1);
//给定两个指针
start=1;
end=n;
//只要start没有超过end
while(start<=end)
{
//最小的和最大的相加，判断是否小于载重量
if(a[start]+a[end]<=w)
{
cnt++; //消耗一条船
start++; //start指针向后走
end--; //end指针向前走
}
else
{
cnt++; //最大的独自消耗一条船
end--;
}
}
cout<<cnt;
return 0;
}