如果,我是说如果你像我一样不知道 在结构体里内置比较函数,存储时用优先队列会相反 这件事,建议你回去看看自己内置的比较函数里是否写成了 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;
}