题干：
Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers A = [a1, a2, ..., an] and B = [b1, b2, ..., bn] of length n each which he uses to ask people some quite peculiar questions.
To test you on how good are you at spotting inequality in life, he wants you to find an "unfair" subset of the original sequence. To be more precise, he wants you to select k numbers P = [p1, p2, ..., pk] such that 1 ≤ pi ≤ n for 1 ≤ i ≤ k and elements in P are distinct. Sequence P will represent indices of elements that you'll select from both sequences. He calls such a subset P "unfair" if and only if the following conditions are satisfied: 2·(ap1 + ... + apk) is greater than the sum of all elements from sequence A, and 2·(bp1 + ... + bpk) is greater than the sum of all elements from the sequence B. Also, k should be smaller or equal to because it will be to easy to find sequence P if he allowed you to select too many elements!
Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of elements in the sequences.
On the second line there are n space-separated integers a1, ..., an (1 ≤ ai ≤ 109) — elements of sequence A.
On the third line there are also n space-separated integers b1, ..., bn (1 ≤ bi ≤ 109) — elements of sequence B.
Output
On the first line output an integer k which represents the size of the found subset. k should be less or equal to .
On the next line print k integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the elements of sequence P. You can print the numbers in any order you want. Elements in sequence Pshould be distinct.
Example
Input
5 8 7 4 8 3 4 2 5 3 7
Output
3 1 4 5
题目大意：
麦克有两个只包含正整数的数组 A = [a1, a2, ..., an] 和 B = [b1, b2, ..., bn] ，长度都为 n 。
他现在想要选出 k 个数 P = [p1, p2, ..., pk] 满足 1 ≤ pi ≤ n 并且数组 P 中的数字互不相等。要求P数组满足: 2·(ap1 + ... + apk) 比数组 A 的和大，并且 2·(bp1 + ... + bpk) 比数组 B的和大。当然， k 必须小于等于 ，否则 P 数组太容易选出来了。
请你给出一个合法的方案。
解题报告：
这题显然要贪心，，但是贪心还是有技巧的。。首先我们发现选择的数量当然是越多越好，所以我们肯定要选满n/2+1个数。
预处理一波，读入的时候a和b捆绑读入，，因为他俩要选就是一起选。。这很套路了不说了。
首先按照a数组排序，，然后把所有的数字分成两组，，转化问题变成：使得选出的数分别在两个数组中的和，大于剩下没有选的数的和。我们发现这只是个充分条件，，并不是充分必要条件，也就是说条件加强了 ，但是我们发现对于这道题加强这一步条件后恰好可以构造出一组解。
我们将其两两相邻的数分成一组，每次从这一组中取出一个就行了，所以我们贪心处理只要拿b值较大的那一个即可，因为a肯定是满足递减的也就是不管我们这两个拿哪一个a，都可以干掉下一组的选择的那个a。
这就很美滋滋了，，仔细观察可以发现，其实对于a数组是跨组贪心的，，也就是我们是这一组取一个值，让他大于下一组的值；对于b数组是本组贪心的，，也就是我们选择的这一个 一定是本组的最优。
所以对于这种贪心策略，我们只需要再找一个大于第一组的选择的a就行了（因为不然没有人压过他），对于这种特例我们这样处理：排好序后第一个结构体一定是我们选择的，然后从第二个元素开始往后分组，，这样就有一个好处那就是可以保证后面的贪心一定是正确的，并且我们也有一个元素可以压过第一组的a。。所以贪心结束。写代码就完事了。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
struct Node {
int a,b;
int pos;
} node[MAX];
bool cmp (Node a,Node b) {
if(a.a != b.a) return a.a > b.a;
else return a.b > b.b;
}
int ans[MAX];
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) scanf("%d",&node[i].a),node[i].pos = i;
for(int i = 1; i<=n; i++) scanf("%d",&node[i].b);
sort(node+1,node+n+1,cmp);
int tot = 0;
ans[++tot] = node[1].pos;
for(int i = 2; i<=n; i+=2) {
if(node[i].b >= node[i+1].b) ans[++tot] = node[i].pos;
else ans[++tot] = node[i+1].pos;
}
//if(n%2==0) ans[++tot] = n;
printf("%d\n",tot);
for(int i = 1; i<=tot; i++) printf("%d%c",ans[i],i == tot ? '\n' : ' ');
return 0 ;
} 总结：
这题思维很巧妙啊。。分成两组，，将问题转化成一个充分条件的问题去进行求解，因为这样方便我们构造贪心。还是要从条件入手啊，，告诉你选n/2个数了，分析一下，，也只能分成两组去考虑 这么做了。
京公网安备 11010502036488号