M29896:购物

greedy, http://cs101.openjudge.cn/practice/29896

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int x,n;
    cin>>x>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    if(a[0]>1) {cout<<-1;}
    else{
        if(n==1)cout<<x;
        else{
        int sum=a[0];
        int ans=1;
        for(int i=2;i<=x;i++){
            if(i>sum){
                for(int j=n-1;j>=0;j--){
                    if(a[j]<=sum+1){
                        ans++;
                        sum+=a[j];
                        break;
                    }
                }
            }
        }
        cout<<ans;
    }
    }
    return 0;
}