codeforces+D. Mike and distribution+二维贪心

题目链接：http://codeforces.com/contest/798/problem/D
给你2个序列，要你选择n/2+1个下标，使的两个序列的此下标元素的和*2>该序列的总和。

8+8+3=19 * 2 = 38 > 30
4+3+7=14 * 2 = 28 > 21

思路：把a序列按从大到小排个序，必须选择a[0]
a[1]是当前a中最大的了。当然了也选了一个a，就是选了a[a[1].id]，

然后对每两个a，选一个比较大的B，也就是max(b[a[i].id], b[a[i + 1].id])

这样，B数组是满足的，这很容易证明，因为每一对中，都选了一个较大的。然后加上第一个，总和肯定大于剩下的。

max(b[1], b[2]) >= min(b[1], b[2])

max(b[3], b[4]) >= min(b[3], b[4])

max(b[5], b[6]) >= min(b[5], b[6])

那么全部相加，不等号方向不变。而且开头还有一个b[A[1].id]加了进来，所以是严格大于的。

再来看看A的证明。
第一是选了a[1]
然后选a[2]和a[3]的那个呢？不固定的，还要看B，但是不管，有以下不等式。
a[1] >= any(a[2], a[3])
any(a[2], a[3]) >= any(a[4], a[5])
any(a[4], a[5]) >= any(a[5], a[6])

也就是，你选了一个a[1]，然后a[2]和a[3]选那个是没关系的，可以用a[1]和它比较，然后又因为选了any(a[2], a[3])，那么你a[4]和a[5]选那个是没所谓的，因为可以用any(a[2], a[3])和它比较。

最后，any(a[n - 1], a[n]) > 0，所以是严格大于的。

思考：这题二维贪心第一次遇到，也可以用随机算法做

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int a;
    int i;
}a[100020];
int b[100020];
int n;
vector<int> v;

int ru(node a, node b){return a.a>b.a;}
void tx()
{
    v.push_back(a[0].i);
    for(int i=1;i<n;i+=2)
    {
        int w=a[i].i;
        if(i+1<n&&b[a[i].i]<b[a[i+1].i])/*以b的大小进行选择*/
        {
            w=a[i+1].i;
        }
        v.push_back(w);
    }

    printf("%d\n",v.size());
    for(int i=0;i<v.size();i++)
    {
        printf("%d%c",v[i]+1,i==v.size()-1?'\n':' ');
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i].a);
        a[i].i=i;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    sort(a, a+n, ru);

    tx();

    return 0;
}