[codeforces23C]Oranges and Apples

time limit per test : 1.5 secondsmemory 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.InputThe 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_iai​andoio_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.OutputFor 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.ExamplesInput2 2 10 15 5 7 20 18 1 0 0OutputYES 1 3 YES 1题意给定2n−12n-12n−1个篮子第iii个篮子里面有aia_iai​个苹果和oio_ioi​个橘子询问能否从中取出nnn个篮子,使得你得到的苹果数量是苹果总数的一半以上并且橘子数量也是橘子总量的一半以上。题解考虑构造一组解。我们先把苹果按照从小到大排序下文中的位置为排完序的位置然后取所有位置在2i−1(1lt;ilt;n)2i-1(1lt;ilt;n)2i−1(1in)的篮子如果这n个篮子里面的橘子数量不符合那么就取所有位置为2i(1lt;ilt;n−1)2i(1lt;ilt;n-1)2i(1in−1)的篮子这样隔着取能保证取的苹果的数量一直大于等于苹果总量最后再从没取的篮子里面找一个能让橘子和苹果的数量都是总量的一半以上的即可。#includebits/stdc.h#definell long longusingnamespacestd;structDs{inta,o,sit;voidread(){scanf(%d%d,a,o);}}p[200004];inlinebooldex(Ds A,Ds B){returnA.aB.a?A.oB.o:A.aB.a;}intn;intw33ha(){scanf(%d,n);ll sa0,so0;for(inti1;i2*n-1;i){p[i].read();p[i].siti;sap[i].a;sop[i].o;}sort(p1,p2*n,dex);ll aa0,ao0;for(inti1;i2*n-1;i2){aap[i].a;aop[i].o;}if(aasa/2(sa%2)aoso/2(so%2)){puts(YES);for(inti1;i2*n-1;i2){printf(%d ,p[i].sit);}puts();return0;}aasa-aa;aoso-ao;for(inti1;i2*n-1;i2){ll naaap[i].a;ll noaop[i].o;if(nasa/2(sa%2)noso/2(so%2)){puts(YES);for(intj2;j2*n-1;j2){printf(%d ,p[j].sit);}printf(%d\n,p[i].sit);return0;}}puts(NO);return0;}intmain(){intT;scanf(%d,T);while(T--)w33ha();return0;}