题解：P13646 [NOISG 2016] LunchBox

· · 题解

0：闲话

蒟蒻第一次写题解QAQ

1：做法

~明显~是一道贪心，按照需求量k[i]从小到大排序，然后再拿N一个个减去k[i]，每减去一次，ans就加一，直到N<k[i]为止，最后输出ans即可。
为什么可以贪心？~我也不知道~ 显然，N所能“支付”的学校数量越多越好，并且学校不管要多少饭盒，都只能对答案做出一次贡献，所以选择需求量大的学校和选择需求量小的学校结果是一样的，那么当然是选择需求量小的学校啦！

2:代码

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
    return a<b;//从小到大
}
int main(){
    int n,k,ans=0;
    int a[k+1];
    cin>>n>>k;
    for(int i=1;i<=k;i++)cin>>a[i];
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        if(n<a[i])break;//坑点，千万不要 n<0 break，否则掉大分
        n-=a[i];
        ans++;
    }
    cout<<ans;
    return 0;
}

3：完结散花