time limit per test : 1.5 seconds
memory limit per test : 256 megabytes
分数：2500（补的有趣的老题）
In2N − 12N - 12N−1boxes there are apples and oranges. Your task is to chooseNNNboxes so, that they will contain not less than half of all the apples and not less than half of all the oranges.
Input
The first input line contains one numberTTT— amount of tests. The description of each test starts with a natural numberNNN— amount of boxes. Each of the following2N − 12N - 12N−1lines contains numbersaia_iaiandoio_ioi— amount of apples and oranges in theiii-th box(0 ≤ ai, oi ≤ 109)(0 ≤ a_i, o_i ≤ 10^9)(0≤ai,oi≤109). The sum of N in all the tests in the input doesn’t exceed10510^5105. All the input numbers are integer.
Output
For each test output two lines. In the first line output YES, if it’s possible to chooseNNNboxes, or NO otherwise. If the answer is positive output in the second lineNNNnumbers — indexes of the chosen boxes. Boxes are numbered from111in the input order. Otherwise leave the second line empty. Separate the numbers with one space.
Examples
Input
2 2 10 15 5 7 20 18 1 0 0Output
YES 1 3 YES 1题意：
给定2n−12n-12n−1个篮子，第iii个篮子里面有aia_iai个苹果和oio_ioi个橘子，询问能否从中取出nnn个篮子,使得你得到的苹果数量是苹果总数的一半以上，并且橘子数量也是橘子总量的一半以上。
题解：
考虑构造一组解。
我们先把苹果按照从小到大排序，（下文中的位置为排完序的位置）然后取所有位置在2i−1(1<=i<=n)2i-1(1<=i<=n)2i−1(1<=i<=n)的篮子，如果这n个篮子里面的橘子数量不符合，那么就取所有位置为2i(1<=i<=n−1)2i(1<=i<=n-1)2i(1<=i<=n−1)的篮子，这样隔着取能保证取的苹果的数量一直大于等于苹果总量，最后再从没取的篮子里面找一个能让橘子和苹果的数量都是总量的一半以上的即可。
#include<bits/stdc++.h>#definell long longusingnamespacestd;structDs{inta,o,sit;voidread(){scanf("%d%d",&a,&o);}}p[200004];inlinebooldex(Ds A,Ds B){returnA.a==B.a?A.o<B.o:A.a<B.a;}intn;intw33ha(){scanf("%d",&n);ll sa=0,so=0;for(inti=1;i<=2*n-1;i++){p[i].read();p[i].sit=i;sa+=p[i].a;so+=p[i].o;}sort(p+1,p+2*n,dex);ll aa=0,ao=0;for(inti=1;i<=2*n-1;i+=2){aa+=p[i].a;ao+=p[i].o;}if(aa>=sa/2+(sa%2)&&ao>=so/2+(so%2)){puts("YES");for(inti=1;i<=2*n-1;i+=2){printf("%d ",p[i].sit);}puts("");return0;}aa=sa-aa;ao=so-ao;for(inti=1;i<=2*n-1;i+=2){ll na=aa+p[i].a;ll no=ao+p[i].o;if(na>=sa/2+(sa%2)&&no>=so/2+(so%2)){puts("YES");for(intj=2;j<=2*n-1;j+=2){printf("%d ",p[j].sit);}printf("%d\n",p[i].sit);return0;}}puts("NO");return0;}intmain(){intT;scanf("%d",&T);while(T--)w33ha();return0;}
