Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers A = [a1, a2, ..., an] and B = [b1, b2, ..., bn] of length n each which he uses to ask people some quite peculiar questions.
To test you on how good are you at spotting inequality in life, he wants you to find an "unfair" subset of the original sequence. To be more precise, he wants you to select k numbers P = [p1, p2, ..., pk] such that 1 ≤ pi ≤ n for 1 ≤ i ≤ k and elements in P are distinct. Sequence P will represent indices of elements that you'll select from both sequences. He calls such a subset P "unfair" if and only if the following conditions are satisfied: 2·(ap1 + ... + apk) is greater than the sum of all elements from sequence A, and 2·(bp1 + ... + bpk) is greater than the sum of all elements from the sequence B. Also, k should be smaller or equal to 
Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!
The first line contains integer n (1 ≤ n ≤ 105) — the number of elements in the sequences.
On the second line there are n space-separated integers a1, ..., an (1 ≤ ai ≤ 109) — elements of sequence A.
On the third line there are also n space-separated integers b1, ..., bn (1 ≤ bi ≤ 109) — elements of sequence B.
On the first line output an integer k which represents the size of the found subset. k should be less or equal to 
On the next line print k integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the elements of sequence P. You can print the numbers in any order you want. Elements in sequence P should be distinct.
5 8 7 4 8 3 4 2 5 3 7
3 1 4 5
题意： 长度为n的Array A和B ，要求构造n/2+1个下标，使suma*2 > tota && sumb*2 > totb
思路：两种算法， 玄学随机orz !!!!!!!!!!!! 正规算法贪心
思路：
①.玄学随机
random_shuffle 暴力前n/2+1个 。 不可描述的玄学，暴力美学? ????
以后是不是碰到类似数组满足某种要求的都可以暴力美学(๑•̀ㅂ•́)و✧！
②.正规贪心
1.对于A数组按a[i]递减排序
2.把a[1]选定
3.如果n是奇数，那么n-1是偶数，选一半，对于连续的两个数a[i],a[i+1]，A任意选一个都可以，对B来说，选b[i]和b[i+1]中最大的就可以构造出答案。
4.偶数同上，先选第一个和最后一个，剩下n-2个选一半
///提供2份AC代码
///贪心
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
struct node{
int a,b,index;
}p[N];
bool cmp(node t1,node t2){
return t1.a>t2.a;
}
int main(void){
int n;cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&p[i].a),p[i].index=i;
for(int i=1;i<=n;i++) scanf("%d",&p[i].b);
sort(p+1,p+1+n,cmp);
cout << n/2+1<<endl;
if(n%2==1){
printf("%d ",p[1].index);
for(int i=2;i<=n;i+=2){
// printf("i=%d\n",i);
if(p[i].b>=p[i+1].b) printf("%d ",p[i].index);
else if(p[i].b<p[i+1].b) printf("%d ",p[i+1].index);
}
}
else if(n%2==0){
printf("%d ",p[1].index);
printf("%d ",p[n].index);
for(int i=2;i<=n-1;i+=2){
if(p[i].b>=p[i+1].b) printf("%d ",p[i].index);
else if(p[i].b<p[i+1].b) printf("%d ",p[i+1].index);
}
}
return 0;
}
///玄学随机
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int n;
ll tota,totb;
struct node{
int a,b,index;
}p[N];
bool check(){
ll suma=0,sumb=0;
for(int i=1;i<=n/2+1;i++){
suma+=1ll*p[i].a;
sumb+=1ll*p[i].b;
if(suma*2>tota &&sumb*2>totb ) return true;
}
return false;
}
int main(void){
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&p[i].a),p[i].index=i,tota+=p[i].a;
for(int i=1;i<=n;i++) scanf("%d",&p[i].b),totb+=p[i].b;
cout << n/2+1 <<endl;
while(!check()){
random_shuffle(p+1,p+1+n);
}
for(int i=1;i<=n/2+1;i++) printf("%d ",p[i].index);
puts("");
return 0;
}
京公网安备 11010502036488号