题目大意
给定两个序列a,b,要求找到不多于个下标,使得对于a,b这些下标所对应数的2倍大于所有数之和。
N<=100000,所有输入大于0,保证有解。
因为明确的暗示,所以一定找个。
考虑去掉取整符号,分奇偶讨论。
1 n为奇数
将a从大到小排序,首先取最大的,接着每两个数取其中b较大的。
2 n为偶数
将a从大到小排序,首先取最大的和另一个(都可以),接着每两个数取其中b较大的。
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=;
int n;
struct node
{
int a,b,pos;
}t[N];
bool cmp(node c,node d)
{
return c.a>d.a;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&t[i].a);
for(int i=;i<=n;i++)
scanf("%d",&t[i].b);
for(int i=;i<=n;i++)
t[i].pos=i;
sort(t+,t+n+,cmp);
printf("%d\n",n/+);
printf("%d ",t[].pos);
if(n%==)
{
printf("%d ",t[n].pos);
n--;
}
for(int i=;i<=n;i+=)
if(t[i].b>t[i+].b)
printf("%d ",t[i].pos);
else
printf("%d ",t[i+].pos);
printf("\n");
return ;
}