传送门

找到个互不相等的

使得且

注意你构造的

我是废物^ _ ^

既然不限制,那么令

要大于原数组的一半

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

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

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

至此,废物的思想停止了

正文,上面都是废话

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

然后可以直接选前个元素,这样对最优秀,但是肯定会因此不满足

然后发现可以转化为:选择的数字比没选的数字大即可

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

一组,一组...每组选择值较大的,这样就可以满足

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

一组,一组...按照上面的策略可以满足

同时可以满足,因为第一个位置的一定大于中的

中的一定大于中的

至此问题得到解

我为什么这么菜啊

#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 );
}