1432 独木舟

原题链接

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1432

解题思想

/* 此题为典型的贪心算法题。 首先题目说每个人都能被独木舟承重。 所以只要将每个人的质量从小到大排序， 设置俩个指针i，j，分别指向头跟尾 具体实现看代码。 这里说一下扩展。 如果题目没有说每个人的重量都小于船的承重量，该怎么做？ 直接预处理，成题目的意思，将超重的处理掉 */

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long ll;
ll a[10005];
int n;
ll m;
int main()
{
    scanf("%d%lld", &n,&m);
    for(int i=0; i<n; ++i)
        scanf("%lld",&a[i]);
    sort(a,a+n);
    int i=0, j=n-1;
    int cnt =0;
    while(i<=j)
    {
        if(i==j && a[i] <=m) //最后只剩下一个
        {
            cnt++;
            i++;
        }
        else if(a[i]+a[j] <=m) //这种策略肯定是最小的
        {
            i++;
            j--;
            cnt++;
        }else //一个人坐一个船
        {
            cnt++;
            j--;
        }
    }
    printf("%d",cnt);
    return 0;
}