ACM_Ruin of Titanic（简单贪心）

Ruin of Titanic

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

看完Titanic后，小G做了一个梦。梦见当泰坦尼克号撞到冰山时，自己也在大船上。情况十分危急，不过这个时候船才刚进水，距离船身完全沉没还有一定时间（假如救生的船足够的话可以顺利逃生）。
假设大船上共有n个人，每个人的重量为W1,W2,....,Wn;现在有若干小船，每一只船最大载重为100,且每一艘小船规定最多只能载2人。你能帮焦急的船长算出最少需要多少船只才能使n人顺利逃生吗？

Input:

输入包含多组测试数据。每一组测试第一行输入正整数n(<=10000)表示共n个人。下一行分别输入n个正整数(Wi<=100),表示n个人的体重。

Output:

对于每一组测试，输出至少需要的船只数量，占一行。

Sample Input:

3
40 65 55
2
80 59

Sample Output:

2
2
解题思路：简单贪心。先排序，然后从体重大的往体重小的贪心，如果最大和最小之和不大于100，则i++,m++；否则--j即可，水过！
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
int n,a[maxn],m;
int main(){
    while(cin>>n){
        for(int i=0;i<n;++i)cin>>a[i];
        sort(a,a+n);m=0;
        for(int i=0,j=n-1;i<=j;--j){
            if(a[i]+a[j]<=100){m++;++i;}
            else m++;
        }
        cout<<m<<endl;
    }
    return 0;
}