这两天后缀数组整多了整点有意思的，随机算法。
题意给你两个数组，让你求一个排列使得这个排列对应的两个数组前n/2+1个数之和的二倍大于每个序列总和。
下面先贴下这题正解
二维贪心，按a从大到小排，把第一个拿着，以后每两个里面选一个a的性质可以满足。
b的话就在两个里面选一个b较大的，这样可以保证有一半的b都大于另一半的b。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 typedef long long ll; 5 int n,ans[N],cnt; 6 struct node 7 { 8 int a,b,id; 9 bool operator <(const node &b)const{ 10 return a>b.a; 11 } 12 }q[N]; 13 int main() 14 { 15 scanf("%d",&n); 16 for(int i=1;i<=n;++i)scanf("%d",&q[i].a),q[i].id=i; 17 for(int i=1;i<=n;++i)scanf("%d",&q[i].b); 18 sort(q+1,q+1+n); 19 ans[++cnt]=q[1].id; 20 for(int i=2;i<=n;i+=2) 21 { 22 if(q[i].b>q[i+1].b) 23 ans[++cnt]=q[i].id; 24 else ans[++cnt]=q[i+1].id; 25 } 26 cout<<cnt<<endl; 27 for(int i=1;i<=cnt;++i) 28 cout<<ans[i]<<" "; 29 return 0; 30 }
下面就是随机化了。。。祝大家新年快乐。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 typedef long long ll; 5 int n,ans[N],cnt; 6 ll sa,sb,ssa,ssb; 7 struct node 8 { 9 int a,b,id; 10 }q[N]; 11 int main() 12 { 13 scanf("%d",&n); 14 for(int i=1;i<=n;++i)scanf("%d",&q[i].a),q[i].id=i,sa+=q[i].a; 15 for(int i=1;i<=n;++i)scanf("%d",&q[i].b),sb+=q[i].b; 16 while(1) 17 { 18 random_shuffle(q+1,q+1+n); 19 ssa=ssb=0; 20 for(int i=1;i<=n/2+1;++i){ 21 ssa+=q[i].a;ssb+=q[i].b; 22 } 23 if(ssa*2>sa&&ssb*2>sb){ 24 cout<<n/2+1<<endl; 25 for(int i=1;i<=n/2+1;++i)cout<<q[i].id<<" "; 26 return 0; 27 } 28 } 29 return 0; 30 }