题解 | #发工资#

#include<bits/stdc++.h>
using namespace std;
bool comp(vector<int> a, vector<int> b) {
    return a[0] > b[0];
}
/*
    优先用最大面额的钞票填m，但是不填满
    然后用最小的填，填满
*/
int compute(vector<vector<int>> &money, int m) {
    int res = 0, remain = m;
    int i = 0;
    while(i<money.size() && money[i][0]>=m) {
        res += money[i][1];
        money[i][1] = 0;
        i++;
    }
    money.erase(money.begin(), money.begin()+i);
    while(true) {
        for(int j=0; j<money.size(); j++)
            if(money[j][1] == 0)
                money.erase(money.begin()+j);
        if(money.empty()) return res;
        i = 0;
        while(remain>=money[i][0] && i<money.size()) {
            if(money[i][1]>0) {
                remain -= money[i][0];
                money[i][1]--;
                while(remain<money[i][0] 
                      && i<money.size())
                    i++;
            } else {
                i++;
            }
        }
        i = money.size()-1;
        while(remain>0 && i>=0) {
            if(money[i][1] > 0) {
                remain -= money[i][0];
                money[i][1]--;
            } else {
                i--;
            }
        }
        if(remain <= 0) {
            remain = m;
            res++;
        }
    }
}
int main() {
    int n, m;
    cin>>n>>m;
    vector<vector<int>> money;
    for(int i=0; i<n; i++) {
        vector<int> vec;
        for(int i=0; i<2; i++) {
            int x; cin>>x;
            vec.push_back(x);
        }
        money.push_back(vec);
    }
    sort(money.begin(), money.end(), comp);
    cout<<compute(money, m);
}