是我算法假了吗？

我的思路如下：

考虑以

b

为关键字从小到大排序，然后显然假如我们加入

i

那么。

$b_i$ 成为最大值，答案增加 $a_i+\text{原最大值}-b_i$
$b_i$ 不是最大值，答案白嫖一个 $a_i$

那么对于我们当前答案的最大值然后将小于

b_i

的还没选的值用堆维护，大于

b_i

还没选的值用堆维护，然后动态删除，加入统计即可。

看了同学的代码，他们都不是这样写的，所以是我代码有BUG 还是思路本身有问题？

样例全过

CPP

#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++;
		
	}
}


*/

是我算法假了吗？

讨论操作

回复

相关推荐

是我算法假了吗？