麦克有两个只包含正整数的数组 A = [a1, a2, …, an] 和 B = [b1, b2, …, bn] ，长度都为 n 。

他现在想要选出 k 个数 P = [p1, p2, …, pk] 满足 1 ≤ pi ≤ n 并且数组 P 中的数字互不相等。要求P数组满足: 2·(ap1 + … + apk) 比数组 A 的和大，并且 2·(bp1 + … + bpk) 比数组 B 的和大。当然， k必须小于等于 ，否则 P 数组太容易选出来了。

请你给出一个合法的方案。

解题思路：

玄学做法：通过随机乱序原数组，然后判断前 ⌊n2⌋+1 个数的和是否满足题意，不满足继续乱序，一直到碰应了结果就输出，有点神奇…

int a[100010],b[100010];
int pos[100010];
int main()
{
   int n;
   long long suma=0,sumb=0;
   scanf("%d",&n);
   for(int i=0;i<n;i++)
    {
       scanf("%d",&a[i]);
       suma+=(long long)a[i];
       pos[i]=i;
    }
   for(int i=0;i<n;i++)
    {
       scanf("%d",&b[i]);
       sumb+=(long long)b[i];
    }
   int num;
   num=n/2+1;
   long long zsa,zsb;
   srand((int)time(0));
   while(1)
    {
       random_shuffle(pos,pos+n);//随机乱序
       zsa=zsb=0;
       for(int i=0;i<num;i++)
       {
           zsa+=(long long)a[pos[i]];
           zsb+=(long long)b[pos[i]];
       }
       if(2*zsa>suma&&2*zsb>sumb)
       {
            printf("%d\n",num);
           printf("%d",pos[0]+1);
           for(int i=1;i<num;i++)
                printf("%d",pos[i]+1);
           printf("\n");
           break;
       }
    }
   return 0;
}

正解：先把a从大到小排序，然后两个两个取其中b的值比较大的。这样做是因为首先a是从大到小排序的了，而且取了一半的数，当前选的肯定比剩下的大，对于b，b取了两者之间比较大的而且选了一半，所以大。这里抓住取了一半这个条件。

对于二维的贪心我们可以先让它变成其中一维有序，这样只需要重点考虑另一维，就会简单很多。