20分往这看
查看原帖
20分往这看
749192
Citrusn楼主2024/9/19 20:47

如果,我是说如果你像我一样不知道 在结构体里内置比较函数,存储时用优先队列会相反 这件事,建议你回去看看自己内置的比较函数里是否写成了 a.b>b.b 如果你也用的反悔贪心的话,只需将 > 改为 < 即可

20分代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;

int n,ans=0,a[N];
int sum=0,b[N];
struct E{
	int b,id;
}p[N];
struct Rule{
	bool operator()(const E &a,const E &b){
		return a.b>b.b;
	}
};
priority_queue< E,vector<E>,Rule >q;


signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=1;i<=n;++i){
		cin>>p[i].b;
		p[i].id=i;
	}
	for(int i=1;i<=n;++i){
		sum+=a[i];
		if(sum<p[i].b){//超过限制——判断是否要后悔 
			if(q.size()&&p[i].b<q.top().b){//后悔 
				sum+=q.top().b-p[i].b;
				q.pop();
				q.push(p[i]);
			}
		}else{//直接加 
			q.push(p[i]);
			sum-=p[i].b;
			++ans;
		}
	}
	int cnt=0;
	while(q.size()){
		b[++cnt]=q.top().id;
//		cout<<b[q.top()]<<'\n';
		q.pop();
	}
	sort(b+1,b+1+cnt);
	cout<<ans<<'\n';
	for(int i=1;i<=cnt;++i){
		cout<<b[i]<<' ';
	}
	return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;

int n,ans=0,a[N];
int sum=0,b[N];
struct E{
	int b,id;
}p[N];
struct Rule{
	bool operator()(const E &a,const E &b){
		return a.b<b.b;//我靠了,存储时用优先队列竟然相反?!?!?!?!!!! 
	}
};
priority_queue< E,vector<E>,Rule >q;


signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=1;i<=n;++i){
		cin>>p[i].b;
		p[i].id=i;
	}
	for(int i=1;i<=n;++i){
		sum+=a[i];
		if(sum<p[i].b){//超过限制——判断是否要后悔 
			if(q.size()&&p[i].b<q.top().b){//后悔 
				sum+=q.top().b-p[i].b;
				q.pop();
				q.push(p[i]);
			}
		}else{//直接加 
			q.push(p[i]);
			sum-=p[i].b;
			++ans;
		}
	}
	int cnt=0;
	while(q.size()){
		b[++cnt]=q.top().id;
//		cout<<b[q.top()]<<'\n';
		q.pop();
	}
	sort(b+1,b+1+cnt);
	cout<<ans<<'\n';
	for(int i=1;i<=cnt;++i){
		cout<<b[i]<<' ';
	}
	return 0;
}
2024/9/19 20:47
加载中...