刚开始一看这不01背包
一看数据nm炸了
特点是v只可能是1或者2
而2=1+1
建两个大根堆,每次拎q1的两个头出来和q2的一个头出来比较
一个很小的优化就是如果v为奇数,那么q1的最大肯定要先取
——-----
最近状态很烂,补一个死活卡在21不知道re在哪里的代码
#include<bits/stdc++.h> using namespace std; struct lys{ long long id,val; bool operator < (const lys a)const{ return val<a.val; } }; long long pri[100000]; priority_queue<lys,vector<lys>,less<lys>>q1; priority_queue<lys,vector<lys>,less<lys>>q2; int main( ) { //freopen("lys.in","r",stdin); long long n,vv; cin>>n>>vv; for(long long i=1;i<=n;i++) { long long t,p; cin>>t>>p; lys son; son.id=i; son.val=p; if(t==1) q1.push(son); else q2.push(son); } long long ans=0,cnt=0; if(vv%2==1&&q1.empty( )==false) { lys now=q1.top( ); ans+=now.val; q1.pop( ); cnt++; pri[cnt]=now.id; vv--; } for(long long v=0;v<=vv;) { if(v==vv) break; lys a1,a2,a3; if(q1.empty( )==false) { a1=q1.top();q1.pop(); } else a1.val=0; if(q1.empty( )==false) { a2=q1.top();q1.pop(); } else a2.val=0; if(q2.empty( )==false) { a3=q2.top(); } else a3.val=0; if(a1.val+a2.val>=a3.val) { ans+=a1.val+a2.val; cnt++; pri[cnt]=a1.id; cnt++; pri[cnt]=a2.id; } else if(a3.val>a1.val+a2.val) { ans+=a3.val; cnt++; pri[cnt]=a3.id; q1.push(a1);q1.push(a2); q2.pop( ); } v+=2; } cout<<ans<<endl; for(long long i=1;i<=cnt;i++) { cout<<pri[i]<<" "; } }