模板思考之反悔贪心（未完成）
2026-01-10 18:39:51
发布于：上海
14阅读
0回复
0点赞
丢个链接链接描述
这道题目是反悔贪心的模板。
单个人认为就算是模板也很有值得深思的地方吧。
先将代码放出：（方便后续解读）
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
struct Node{
ll t1,t2;
//修理这个建筑需要T1时间，需要在T2秒内完成这个建筑的修复。
friend bool operator < (Node a,Node b){
return a.t1<b.t1;
}
}node[N];
priority_queue<Node>pq;
bool cmp(Node a,Node b){
return a.t2<b.t2;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>node[i].t1>>node[i].t2;
sort(node+1,node+1+n,cmp);
ll now=0;
int ans=0;
for(int i=1;i<=n;i++){
//cout<<node[i].t1<<" "<<node[i].t2<<" "<<now<<endl;
if(node[i].t1+now<=node[i].t2){
pq.push(node[i]);
now+=node[i].t1;
ans++;
}else if(pq.size()&&node[i].t1<pq.top().t1){
Node sum=pq.top();
pq.pop();
now-=sum.t1;
now+=node[i].t1;
pq.push(node[i]);
}
}
cout<<ans;
return 0;
}
先说说整体的思路吧：
因为是反悔贪心的模板，所以整体必然是反悔贪心。
怎么贪：
模板大概是这样的一个结构（整体分为两个部分）：
1.排序
2.反悔贪心
对这两个部分，我提出几个问题：
Q1：
还是直接证贪心吧
有帮助，赞一个