题目描述

难度分:$2500$

输入$T$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$表示有$2n-1$个盒子。

然后输入$2n-1$行，每行$2$个数字$a[i]$和$o[i]$，表示第$i$个盒子中的苹果个数和橘子个数，元素范围$[0,10^9]$。

你需要从这$2n-1$个盒子中，选出$n$个盒子。能否使这$n$个盒子中的苹果个数之和$\geq \frac{\Sigma_{i=1}^{2n-1}a[i]}{2}$，且橘子个数之$\geq \frac{\Sigma_{i=1}^{2n-1}o[i]}{2}$？

如果不能，输出NO，否则输出YES和你选的这$n$个盒子的编号（按照输入的顺序，编号从$1$开始）。

输入样例

2
2
10 15
5 7
20 18
1
0 0

输出样例

YES
1 3
YES
1

算法

数学

这个题的感觉就是从哪个数学竞赛挖过来的，对$a$升序排列，那么以下两种方案必然有一种是可以的：

1. 选择$a_1,a_3,…,a_{2n-5},a_{2n-3},a_{2n-1}$。
2. 选择$a_2,a_4,…,a_{2n-4},a_{2n-2},a_{2n-1}$。

如果是方案一，由于$a_{2k+1} \geq a_{2k},k \in N^*$成立，再算上$a_1$，方案一的总苹果数一定不会少于总数的一半。

如果是方案二，由于$a_{2k} \geq a_{2k-1},k \in N^*$，再算上$a_{2n-1}$，方案二的总苹果数一定不会少于总数的一半。

此时我们就只需要证明这两种方案对应的橘子总数不可能都少于橘子总数的一半即可。设橘子总数为$s$，且满足以下两个不等关系：

1. $s_1=o_1+o_3+…+o_{2n-5}+o_{2n-3}+o_{2n-1} \lt \frac{s}{2}$
2. $s_2=o_2+o_4+…+o_{2n-4}+o_{2n-2}+o_{2n-1} \lt \frac{s}{2}$。

那么就有$s_1+s_2+2o_{2n-1} \lt s$，而$s=s_1+s_2+o_{2n-1}$，这就会推出$o_{2n-1} \lt 0$，矛盾。所以本题一定有解，我们只需要检查一下两种方案哪种可以，然后输出那个可以的方案就行。

复杂度分析

时间复杂度

排序之后的判断是$O(n)$的，只需要遍历数组，因此算法的性能瓶颈在于排序，时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$a$数组和$o$数组，仅使用了有限几个变量，因此空间瓶颈也在于排序，快排的额外空间复杂度为$O(log_2n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n;
LL tot_a, tot_o;

struct Box {
    int i, a, o;
    bool operator<(const Box other) const {
        return a < other.a;
    }
} boxes[N];

bool solve(int tp) {
    LL sum_o = boxes[2*n - 1].o;
    for(int i = tp; i < 2*n - 1; i += 2) {
        sum_o += boxes[i].o;
    }
    return 2*sum_o >= tot_o;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        tot_a = tot_o = 0;
        for(int i = 1; i <= 2*n - 1; i++) {
            scanf("%d%d", &boxes[i].a, &boxes[i].o);
            boxes[i].i = i;
            tot_a += boxes[i].a;
            tot_o += boxes[i].o;
        }
        sort(boxes + 1, boxes + 2*n);
        puts("YES");
        if(solve(1)) {
            for(int i = 1; i <= 2*n - 1; i += 2) {
                printf("%d ", boxes[i].i);
            }
            puts("");
        }else {
            for(int i = 2; i <= 2*n - 1; i += 2) {
                printf("%d ", boxes[i].i);
            }
            printf("%d\n", boxes[2*n - 1].i);
        }
    }
    return 0;
}