独木舟问题

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

输入

第一行包含两个正整数n (0<n<=10000)和m (0<m<=2000000000)，表示人数和独木舟的承重。
接下来n行，每行一个正整数，表示每个人的体重。体重不超过1000000000，并且每个人的体重不超过m。

输出

 

一行一个整数表示最少需要的独木舟数。

 

输入示例

3 6
1
2
3

输出示例

2

 贪心思想：就是判断最重的那个人能不能和最轻的那个人同一条船，如果不能，则最重的人一定是一个人一条船

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

ll a[10005];
int main(){
    ll n, m;
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    sort(a, a+n);
    ll k=0;
    for(int i=n-1; i>=0; i--){
        int s=0;
        if(a[i]==0){
            break;　　　　　　//如果搜到了a[i]=0的点，说明分配完毕，结束循环
        }
        while(a[s]==0){
            s++;
        }
        if((a[s]+a[i])>m){　　//具体实现细节，从最重的人开始枚举，如果最轻的人能和最重的人坐一条船，就把最轻的人弄出去，设a[i]=0
            a[i]=0;
            k++;
        }else{
            a[i]=a[s]=0;
            k++;
        }
    }
    cout << k << endl;
    return 0;
}