1 solutions

  • 1
    @ 2022-9-11 22:44:14

    贪心

    策略就是每次卖给别人品质最差的奶牛,用multiset

    #include <iostream>
    #include <set>
    
    const int maxn = 1e6 + 5;
    
    int n, op[maxn], num[maxn], ans;
    
    int main() {
        using std::cin;
        using std::cout;
        using std::endl;
        
        std::ios::sync_with_stdio(false);
    
        cin.tie(nullptr);
    
        cin >> n;
    
        std::multiset<int> s;
        
        for(int i = 1; i <= n; i++) cin >> op[i] >> num[i];
        
        for(int i = n; i >= 1; i--) {
            if(op[i] == 1) {
                s.insert(num[i]);
            } else if(!s.empty()) {
                auto iter = s.lower_bound(num[i]);
                if(iter == s.end()) iter--;
                for(;;) {
                    if(*iter <= num[i]) {
                        ans++;
                        s.erase(iter);
                        break;
                    }
                    if(iter == s.begin()) break;
                    iter--;
                };
            }
        }
        
        cout << ans << endl;
    
        return 0;
    }
    
    • 1

    Information

    ID
    155
    Time
    3000ms
    Memory
    512MiB
    Difficulty
    8
    Tags
    # Submissions
    329
    Accepted
    44
    Uploaded By