题目类型 想法题
题目意思
输入一个n (n <= 1e5), 表示接下来有 2*n-1 个盒子, 每个盒子有 a 个橘子和 b 个苹果, 现在要求你从 2*n-1 个盒子中选出 n 个盒子
使这 n 个盒子里的橘子的总数不小于橘子总数的一半, 苹果的总数不小于苹果总数的一半
解题方法
把 2*n-1 个盒子按橘子的数量从小到大排序, 然后对于下标为奇数(下标从1开始)的盒子, 如果这些盒子的苹果数符合要求
则结果为这些下标为奇数的例子, 否则结果为下标为偶数的盒子再加上最后一个盒子
因为假设有7个盒子 (a表示橘子, b表示苹果, Suma表示橘子总数, Sumb表示苹果总数)
a1 + a3 + a5 + a7 肯定大于等于 a2 + a4 + a6 (因为 a7>=a6 a5>=a4 a3>=a2 a1>=0) 即 a1+a3+a5+a7 >= Suma / 2
那么如果 b1 + b3 + b5 + b7 >= Sumb / 2 显然结果为 1 3 5 7 (橘子和苹果都满足条件了)
但是如果 1 3 5 7这些盒子不满足条件即 b1+b3+b5+b7 < Sumb/2 那么 (b2,b4,b6,b7)肯定满足 即选择 2 4 6 7, 因为
对于a的话 a6 >= a5, a4 >= a3, a2 >= a1 a7 >= 0 即橘子满足了
对于苹果
b1+b2+b3+b4+b5+b6+b7 = Sumb
现在如果 b1+b3+b5+b7 < Sumb/2 即
Sumb-(b2+b4+b6) < Sumb/2 那么把(b2+b4+b6)拿到左边 ->
(b2+b4+b6) > Sumb/2, 即 a2+a4+a6+a7 > Sumb/2
Sumb-(b2+b4+b6) < Sumb/2 那么把(b2+b4+b6)拿到左边 ->
(b2+b4+b6) > Sumb/2, 即 a2+a4+a6+a7 > Sumb/2
苹果也能满足了
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <string> #include <algorithm> using namespace std; typedef long long LL; const int MAXN = 1e5*2 + 10; struct P{ int a, b, pos; }p[MAXN]; bool cmp(const P & a, const P & b) { return a.a < b.a; } int main() { int t; scanf("%d", &t); while(t--) { int n; LL suma = 0, sumb = 0; scanf("%d", &n); for( int i=1; i<=2*n-1; i++ ) { scanf("%d%d", &p[i].a, &p[i].b); suma += p[i].a; sumb += p[i].b; p[i].pos = i; } sort(p+1, p + 2*n-1+1, cmp); LL t1 = 0, t0 = 0; for( int i=1; i<=2*n-1; i++ ) { if(i&1) t1 += p[i].b; else t0 += p[i].b; } if(t1 * 2 >= sumb) { printf("YES\n"); for( int i=1; i<=2*n-1; i++ ) { if(i&1) printf("%d ", p[i].pos); } printf("\n"); } else if((t0 + p[2*n-1].b)*2>=sumb) { printf("YES\n"); for( int i=1; i<=2*n-1; i++ ) { if(i%2==0) printf("%d ", p[i].pos); } printf("%d\n", p[2*n-1].pos); } else printf("NO\n"); } return 0; }