目录
cf865D
环形喂猪
建筑抢修
cf865D
思路：
我们贪心的原则是尽可能的多卖，而且尽可能的卖的多。
整体的贪心思路就是能卖就卖，卖完后放入堆中（以便反悔），先不考虑能卖多少，因为堆是按照价格从小到大排序，把最优的选择放在最前面。
在遍历到第i天时候，如果我们当前卖是可以获利的，那就直接卖掉，然后把价格放入反悔堆。
如果后面还有更大的pk，那么我们可以在pi处撤销丢弃操作（也就是把pi买下来），然后在pk处丢弃。操作就是再加上pk-pi即可。
贪心就是：能卖，我们就卖，不过卖完后要把此点加入堆中，以便我们可以反悔。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll ans;
priority_queue<int,vector<int>,greater<int> >heap;//小根堆
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int p;cin>>p;
if(heap.size()&&heap.top()<p){
ans+=p-heap.top();
heap.pop();
heap.push(p);
}
heap.push(p);
}
cout<<ans;
}
环形喂猪
思路：
一道非常典型的反悔贪心，反悔贪心就是我们需要建立一个贪心堆，先按照正常的思路（局部最优）进行贪心，如果当前取出的不是最优解，那就反悔。
我们把所有的猪放入堆中，取出一个最大猪，然后标记左右节点，并把这三个节点删掉，但是又要考虑到方便反悔，而反悔操作应该是a[i-1]+a[i+1]，而我们现在已经取了a[i]，所以应该把a[i-1]+a[i+1]-a[i]直接加入堆中，并创建新的节点。以方便反悔。
#include <bits/stdc++.h>
using namespace std;
const int N=4e+5;
bool mark[N];
int n,m,l[N],r[N],ans,a[N],tot;
struct node{
int id,v;
};
priority_queue<node>q;
bool operator<(const node &x,const node &y){
return x.v<y.v;
}
int main(){
cin>>n>>m;
if(m>n/2){
cout<<"Error!";return 0;
}
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<n;i++){
l[i]=i-1,r[i]=i+1; //创建环形链表
q.push({i,a[i]});//加入大根堆
}
l[1]=n;r[1]=2;l[n]=n-1;r[n]=1;//起点和尾点
q.push({1,a[1]});q.push({n,a[n]});
tot=n;
for(int i=1;i<=m;i++){
node cur;cur=q.top();q.pop();
if(mark[cur.id]){i--;continue;}//已经被删掉的点就跳过，注意i--，别又浪费了一袋
ans+=cur.v;//更新答案
a[++tot]=a[l[cur.id]]+a[r[cur.id]]-a[cur.id];//创建反悔点
q.push({tot,a[tot]});//反悔点入堆
l[tot]=l[l[cur.id]];r[tot]=r[r[cur.id]];//更新新节点的左右关系
r[l[l[cur.id]]]=tot;l[r[r[cur.id]]]=tot;//新节点的左右节点的指向新节点
mark[cur.id]=mark[l[cur.id]]=mark[r[cur.id]]=1;//删掉3个点
}
cout<<ans;
return 0;
}
建筑抢修
思路：
我们贪心的原则是先去修那些代价比较小且很容易报废的建筑（t2比较大的建筑），
如何去修容易报废的建筑呢？那就是按照t2从大到小进行排序进去“抢修”。
所以最开始，我们先按照能修就修的原则去修每一个建筑，然后把修的建筑放入堆中（以便反悔），堆是按照代价排序，以便把最坏的决定放到堆头。
如果当前的建筑可以抢修，那么就直接修，修后放入反悔堆。
如果当前的建筑来不及抢修，我们就去“反思自己”，看看已经修的建筑中有没有代价比这个建筑大的，如果有，那么就反悔time-=heap.top().t1; time+=a[i].t1;之前的出去，新的进来。如果没有，那就直接不用反悔。
#include <bits/stdc++.h> //p4053建筑抢修
using namespace std;
const int N=150005;
int n;
struct node{
long long t1,t2;
}a[N];
bool operator<(const node &p,const node &q){
return p.t1<q.t1;
}
bool cmp (const node p,const node q){
return p.t2<q.t2;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
long long t1,t2;cin>>t1>>t2;
a[i]=(node){t1,t2};
}
sort(a,a+n,cmp);
priority_queue<node>heap;//大根堆
long long time=0;//time里面是已经建好所耗费的时间，建的东西在堆中
for(int i=0;i<n;i++){
if(a[i].t2>=time+a[i].t1){//正常贪心（能建就去建）
time+=a[i].t1;
heap.push(a[i]);
}
else{
if(a[i].t1<heap.top().t1){//（反悔贪心）我们之间建了一个很耗时间的房子，现在应该把它替换掉
time-=heap.top().t1;
heap.pop();
time+=a[i].t1;
heap.push(a[i]);
}
}
}
cout<<heap.size();
}
