先按照等级从小到大排序。
考虑先二分答案,把所有等级符合要求的三元组存下来,随机顺序贪心即可。
更具体地,开一个vector
把所有符合要求的三元组存下来,贪心的时候,如果当前的和之前的和为质数,那就不选,否则选。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #pragma GCC optimize("Ofast,no-stack-protector") #include<bits/stdc++.h> using namespace std; struct node{int x,y,z;}a[105]; int n,k,p[10000005],v[10000005],cnt; mt19937 rd((unsigned long long)new char); bool check(int mid){ vector<node>b,chz; for(int i=1;i<=n&&a[i].z<=mid;++i)b.push_back(a[i]); int ans=0; for(int i=1;i<=300;++i){ int sum=0; for(int j=0;j<b.size();++j){ int flag=1; for(auto[x,y,z]:chz) if(!v[b[j].y+y]){flag=0;break;} if(flag){chz.push_back(b[j]);sum+=b[j].x;} } ans=max(ans,sum); chz.clear(); shuffle(b.begin(),b.end(),rd); } return ans>=k; } int main(){ for(int i=2;i<=10000000;++i){ if(!v[i]){ p[++cnt]=i; for(int j=i*2;j<=10000000;j+=i)v[j]=1; } } cin>>n>>k; for(int i=1;i<=n;++i)cin>>a[i].x>>a[i].y>>a[i].z; sort(a+1,a+n+1,[&](node x,node y){return x.z<y.z;}); int l=1,r=n+1; while(l<r){ int mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1; } if(l>n)cout<<"-1\n"; else cout<<l<<'\n'; return 0; }
|