CF23C Solution

题目链接

题解

将箱子按照(a_i)升序排序，将其如→((a_1,a_2),(a_3,a_4),cdots,(a_{n-2},a_{n-1}),(a_n))两两分组。可以发现每个括号中选择一个元素，和一定大于一半。小证明：如果全部选择(a_1,a_3,a_5,cdots,a_{n-2},a_n)（最小的选择），则(a_nge a_{n-1},a_{n-2}ge a_{n-3},cdots ,a_3ge a_2)，并另多一个(a_1)。因此我们每次选择括号中(o_i)较大的一项，易得这样便同时满足选出的(a,o)之和均大于一半。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node {int a,o,id;} b[2*N];
bool cmp(node x,node y) {return x.a<y.a;}
int main()
{
	int t,n,cnt1,cnt2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<2*n;i++) {scanf("%d%d",&b[i].a,&b[i].o); b[i].id=i;}
		sort(b+1,b+2*n,cmp); 
		printf("YES
");
		for(int i=1;i<2*n-1;i+=2)
		{
			if(b[i].o>b[i+1].o) printf("%d ",b[i].id);
			else printf("%d ",b[i+1].id);
		}
		printf("%d
",b[2*n-1].id);
	}
	return 0;
}