我是废物^ _ ^

既然不限制 $k$ ,那么令 $k=\frac{\lfloor n\rfloor}{2}+1$

要大于原数组的一半

不妨先满足 $a$ 数组,挑选 $a$ 最大的 $k$ 个下标 $p_i$

那么如何调整让 $b$ 数组也满足条件?

是不是选择最大的 $b_i$ 的下标会比较好呢?但是如果相应的 $a_i$ 非常小呢?无法抉择,抛弃这种想法...

~~至此,废物的思想停止了~~

正文,上面都是废话

一共有 $n$ 组数据,先按照 $a$ 为关键字排序

然后可以直接选前 $n/2+1$ 个元素,这样对 $a$ 最优秀,但是 $b$ 肯定会因此不满足

然后发现 $2\sum a_{p_i}>\sum a_i$ 可以转化为:选择的数字比没选的数字大即可

因为需要选一半的数字,那就两个两个来考虑

$(1,2)$ 一组, $(2,3)$ 一组...每组选择 $b$ 值较大的,这样就可以满足 $b$

但是不一定可以满足 $a$ ...但是如果我们一开始把排序后位置 $1$ 选掉

$(2,3)$ 一组, $(4,5)$ 一组...按照上面的策略可以满足 $b$

同时可以满足 $a$ ,因为第一个位置的 $a$ 一定大于 $(2,3)$ 中的

$(2,3)$ 中的 $a$ 一定大于 $(4,5)$ 中的

至此问题得到解

~~我为什么这么菜啊~~

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct p{int a,b,id;}d[maxn]; int n;
bool com( p a,p b ){ return a.a>b.a; }
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)    cin >> d[i].a;
    for(int i=1;i<=n;i++) { cin >> d[i].b; d[i].id = i; }
    sort( d+1,d+1+n,com );
    printf("%d\n%d ",n/2+1,d[1].id);
    for(int i=2;i<=n;i+=2)    printf("%d ",d[i+(d[i].b<d[i+1].b)].id );
}

D. Mike and distribution

我是废物^ _ ^