/*
CF410div2 D. Mike and distribution
http://codeforces.com/contest/798/problem/D
构造
题意:给出两个数列a,b,求选出n/2+1个数对,使得其和的二倍大于各自的数列
思路:对数列a进行排序,因为可以选一半加1个,所以最大的那个我们选出来
然后在剩下的数列中,每隔两个选则b中较大的,
这样可以保证选出的在b中满足条件,并且在a中也满足条件
然而。。。。我他喵的居然忘了读入b数列!!!!
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e6+;
long long a[Nmax],b[Nmax];
int m;
long long s1,s2;
long long now1,now2;
int book[Nmax];
struct Node
{
int a;
int id;
}num[Nmax];
bool cmp(Node a,Node b)
{
return a.a>b.a;
}
int ans[Nmax];
int main()
{
#ifdef test
#endif
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
num[i].id=i;
num[i].a=a[i];
}
for(int i=;i<=n;i++)//忘了读入b[],真是醉了,感觉最近不适合写代码。。。
scanf("%lld",&b[i]);
sort(num+,num++n,cmp);
int ans_size=;
int i=;
ans[++ans_size]=num[i++].id;
for(;i<=n;i+=)
{
if(i==n)
{
ans[++ans_size]=num[i].id;
break;
}
if(b[num[i].id]>b[num[i+].id])
ans[++ans_size]=num[i].id;
else
ans[++ans_size]=num[i+].id;
}
printf("%d\n",ans_size);
for(int i=;i<=ans_size;i++)
printf("%d%c",ans[i],i==ans_size?'\n':' ');
return ;
}
05-15 05:47
查看更多