codeforces23C Oranges and Apples

题目大意

题意是给定2*N-1个篮子里面分别含有ai个苹果bi个橘子问能否选择出N个篮子使得所有篮子里面的苹果个数大于等于总苹果个数的一半且所有的橘子个数大于等于所有橘子个数的一半

思路

我们按照一个值排序，这里选择苹果把他升序排列然后我们按照奇数下标选取橘子或者按照偶数下标选取，如果按照奇数下标选取的橘子满足条件那么就是这么选否则是偶数下标加上2*N-1下标

解释

首先我们这么做能保证苹果是一定满足条件的因为an>an-1 an-2>an-3 … a3>a1所以加起来也一定是满足条件的，那么剩下的就是如果奇数个橘子满足条件那么就是否则就选偶数个再加最后一个
我们假设奇数个橘子的重量为A,那么偶数个为A’那么A+A’=sum且A < sum/2 那么sum-A’ < sum/2 移项得到 A’ > sum/2 再加上最多的苹果肯定是满足条件的且现在苹果满足a2>a1 a4>a3 再加上一个a2*n-a肯定也是满足条件的

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
struct node
{
	long long l,r,id;
}a[N],b[N];
bool c1(node a,node b)
{
	return a.l<b.l;
}
bool c2(node a,node b)
{
	return a.id<b.id;
}
int main()
{
	ios::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--)
	{
		long long jk1=0,jk2=0,s1=0,s2=0;
		int n,p=0;
		cin>>n;
		for(int i=1;i<=2*n-1;i++)
		cin>>a[i].l>>a[i].r,jk1+=a[i].l,jk2+=a[i].r,a[i].id=i;
		sort(a+1,a+2*n,c1);
		for(int i=1;i<=2*n-1;i++)
		if(i&1) s1+=a[i].r;
		else s2+=a[i].r;
		if(s1>=jk2/2+(jk2%2!=0))
		{
			cout<<"YES\n";
			for(int i=1;i<=2*n-1;i+=2)
			b[++p]=a[i];
			sort(b+1,b+1+p,c2);
			for(int i=1;i<=p;i++)
			cout<<b[i].id<<" ";
			cout<<"\n";
		}
		else if(s2>=jk2/2+(jk2%2!=0))
		{
			cout<<"YES\n";
			b[++p]=a[2*n-1];
			for(int i=2;i<=2*n-1;i+=2)
			b[++p]=a[i];
			sort(b+1,b+1+p,c2);
			for(int i=1;i<=p;i++)
			cout<<b[i].id<<" ";
			cout<<"\n";
		}
		else
		cout<<"NO\n";
	}
}