1 solutions
-
1
贪心
策略就是每次卖给别人品质最差的奶牛,用
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