51nod贪心算法入门-----独木舟问题

独木舟问题

n个人，已知每个人体重，独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？

分析：按照人的体重排序，最轻的人跟最重的人尽量安排在一条船上，如果超过就安排最重的.

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        int i,j,ans=0;
        int a[10001];
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        j=n-1;
        i=0;
        while(i<j){
            if(a[i]+a[j]<=m){
                ans++;
                i++;
                j--;
            }
            else{
                ans++;
                j--;
            }
        }
        if(i==j)
            ans++;
        printf("%d\n",ans);
    }
}