随机化求调1关
查看原帖
随机化求调1关
578029
ivyjiao楼主2024/3/5 20:26
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[200001],b[200001],c[200001],suma,sumb;
signed main(){
    cin>>t;
    for(int j=1;j<=t;j++){
        suma=0;
        sumb=0;
        cin>>n;
        for(int i=1;i<=2*n-1;i++) cin>>a[i]>>b[i],c[i]=i;
        for(int i=1;i<=2*n-1;i++) suma+=a[i],sumb+=b[i];
        while((double)clock()<CLOCKS_PER_SEC*0.99/t*j){
            random_shuffle(c+1,c+2*n);
            int cnt1=0,cnt2=0;
            for(int i=1;i<=n;i++) cnt1+=a[c[i]],cnt2+=b[c[i]];
            if(cnt1*2>=suma&&cnt2*2>=sumb){
                cout<<"YES"<<endl;
                for(int i=1;i<=n;i++) cout<<c[i]<<" ";
                cout<<endl;
                break;
            }
        }
    }
}
2024/3/5 20:26
加载中...