先按照最晚修理时间进行排序,从最早的开始进行遍历。进来后如果可以达到最晚修理时间那么直接加入即可,如果达不到的话,与我已有的建筑的修理时间进行比较如果修理时间比原有的小的话那么就需要对原来的建筑进行一个调整,如果大的话不变就行,总之是一个一换一的过程,但同时也为后面腾出了更多的修理时间,所以贪心成立。因为要比较最大的那一个所以维护一个大根堆比较方便。
#include <bits/stdc++.h> typedef long long ll; using namespace std; int N; const int maxn = 150000+10; struct Node{ ll t1; ll t2; } node[maxn]; priority_queue<ll> pq; bool comp(Node n1, Node n2) { return n1.t2<n2.t2; } int main() { cin>>N; for (int i=0;i<N;i++) { cin>>node[i].t1; cin>>node[i].t2; } sort(node, node+N, comp); int cnt = 0; for (int i=0;i<N;i++) { if (cnt+node[i].t1<=node[i].t2) { pq.push(node[i].t1); cnt+=node[i].t1; } else { if (pq.top()>node[i].t1) { cnt -= pq.top(); pq.pop(); cnt += node[i].t1; pq.push(node[i].t1); } } } cout<<pq.size(); return 0; }