我的思路如下:
考虑以 b 为关键字从小到大排序,然后显然假如我们加入 i 那么。
bi 成为最大值,答案增加 ai+原最大值−bi
bi 不是最大值,答案白嫖一个 ai
那么对于我们当前答案的最大值然后将小于 bi 的还没选的值用堆维护,大于 bi 还没选的值用堆维护,然后动态删除,加入统计即可。
看了同学的代码,他们都不是这样写的,所以是我代码有BUG 还是思路本身有问题?
样例全过
#include<bits/stdc++.h>
using namespace std;
struct node{
int a;
long long b;
}p[200005];
bool cmp(node x,node y){
if(x.b==y.b)return x.a>y.a;
return x.b<y.b;
}
int n,ind,cnt;
long long maxb,ans;
priority_queue<pair<long long,int> >q1;
priority_queue<pair<long long,int> >q2;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b;
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++){
q2.push(make_pair(p[i].a-p[i].b,i));
}
maxb=0;
ind=1;
while(cnt<n){
pair<long long,int>l;
if(!q1.empty())l=q1.top();
else l.first=-1e18;
pair<long long,int>r;
while(!q2.empty()&&q2.top().second<ind)q2.pop();
if(!q2.empty())r=q2.top();
else r.first=-1e18;
if(r.first+maxb>=l.first){
ans+=maxb+r.first;
maxb=p[r.second].b;
q2.pop();
while(ind<r.second){
q1.push(make_pair(p[ind].a,ind));
ind++;
}
ind++;
}else{
ans+=l.first;
q1.pop();
}
cout<<ans<<endl;
cnt++;
}
}
*/