题目链接
题目大意：
在 2 * n -1 个盒子里，有 苹果 和 橘子 ，每个盒子 从 1 开始编号 ， 让你挑选 n 个盒子，并且里面的苹果数量不少于总苹果的数量，橘子的数量也不少于总橘子的数量
解题思路：
一开始我写了两个排序。。。然后 wa2 了 ，看了题解，哦，思维题
把 苹果 从小到大 排序，然后排完序后的奇数位置的苹果 一定是 大于偶数 位置的 苹果的
比如 a[1] + a[3] + a[5] > a[2] + a[4]
因为 a[5] > a[4] , a[3] > a[2] 还多了个 a[1]
或者 偶数位置的加上最后位置的 一定大于其它位置的
比如 a[2] + a[4] + a[5] > a[1] + a[3]
因为 a[2] > a[1] , a[4] > a[3] 还多了个 a[5]
这样苹果任意一种都满足了 选择哪种就看橘子了
橘子呢 先统计下橘子的总数量 然后 按照第一种统计下橘子的数量 即所有奇数位置的橘子数量 如果满足条件 就输出位置
不然 就输出偶数位置加 最后一个 肯定是满足的
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6;
long long a[maxn];
struct node
{int d;long long a;long long o;
}e[maxn];
bool cmp(node x,node y)
{return x.a<y.a;
}
int main()
{int t;int n;int i,j;cin>>t;long long ans=0;long long sum=0;while(t--){cin>>n;sum=0;ans=0;for(i=1;i<=2*n-1;i++){cin>>e[i].a>>e[i].o;e[i].d=i;sum+=e[i].o;}sort(e+1,e+2*n,cmp);cout<<"YES"<<endl;for(i=1;i<=2*n-1;i++){if(i%2!=0)ans+=e[i].o;}if(ans*2>=sum){for(i=1;i<=2*n-1;i++){if(i%2){cout<<e[i].d<<" ";}}cout<<endl;}else{for(i=1;i<=2*n-1;i++){if(i%2==0){cout<<e[i].d<<" ";}}cout<<e[2*n-1].d<<endl;}}return 0;
}