题解 | #发工资#

1. 贪心法，只过了6/10. 但基本思想应该是这样。
2. 大的方面，钱数弄完为止
3. 钱按照面额从大到小排序。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,x,y;
    long long m;

    vector<pair<long long, int>> v;

    while(cin>>n>>m){
        v.clear();
        int cnt = 0;//有多少张
        for(int i=0; i<n;i++){
            cin>>x>>y;
            v.push_back({x,y});
            cnt+=y;//总的张数
        }
        sort(v.begin(),v.end(),[](pair<long long, int> a,pair<long long, int> b){
            return a.first>b.first;//从大到小排序
        });

        int ret = 0;//结果记录
        int start = 0; //第一个小于面额的钱。下标
        //先处理大的钱
        for(int i =0;i< n;i++){
            if(v[i].first>=m){
                ret+=v[i].second;//所有大的钱都用了、
                cnt-= v[i].second;
                v[i].second =0;
            }else{
                start= i;
                break;
            }
        }

        //开始以钱的张数(每一个大循环是一轮（一个月工资发放的组合情况）)
        while(cnt>0){
            long long need = m;//
            for(int i = start;i<n;i++){
                int it = i;
                if(v[i].second>0){//前提是必须有这个钱
                    //下面三种判断记得脑海中用适应的动画演示
                    if(v[i].first > need){//如果大于need
                        continue;
                    }else if(v[i].first == need){
                        ret++;//结果出现一个
                        need -= v[i].first;//每次都三步，别忘了
                        v[i].second--;
                        cnt--;
                        break;//退出
                    }else if(v[i].first < need){//如果当前需求比第一个最大的大，那就使劲花第一个最大的那个组合
                        need -= v[i].first;
                        v[i].second--;
                        cnt--;
                        i = it -1;//确保下次回到相同的地方
                        continue;
                    }
                }
            }
             //处理货币剩余面额大于0，从最小的开始遍历

            for(int i= n-1; i>=start;i--){
                if(v[i].second>0){
                    need-= v[i].first;
                    cnt--;
                    v[i].second--;
                    if(need<=0){//小于等于0.建成或者负数为之（组成的签署刚好或者恰好大一点）
                        ret++;
                        break;
                    }
                }
            }
        }
        cout<<ret<<endl;
    }

    return 0;
}