ACM模版

描述

题解

这个题当时我没看懂题，所以没做，后续补题时学到了很多东西~~~好题！

题意大概是，从 A[] 和 B[] 中对应位置分别取不超过 ⌊n2⌋+1 个数，使分别对于 A[] 和 B[] 来说，这些数之和的二倍大于该数组和，也就是说子集的两倍大于数组和，那么等价于所取的数之和大于未取的数之和，所以，这里自然是取数越多越好，最多 ⌊n2⌋+1 个。

这里由于结果不唯一，所以这是一个特判题。这样也就催生出了一种玄学的解法（代码 One），通过随机乱序原数组，然后判断前 ⌊n2⌋+1 个数的和是否满足题意，不满足继续乱序，一直到碰应了结果就输出，GG。这个有些许猴子排序的恶搞趣味，但是你没有看错，这里能够 AC。据我猜测这个之所以可行是因为可行解十分多，所以他乱序碰到答案的可能性比较高，如果对于可行解不多的题，那么这就是贴脸草题，有些考验脸了。

当然，还有比较客观的解法（代码 Two），先根据 A[] 对 pos 排序，然后将最大的入 ans，接着每两个进行一次判断，看哪个 B[] 大，大的入 ans，这样遍历一遍后就是结果了。这里需要强调的一点是必须先将最大的入 ans，不然无法保证 A 的合法性，只有先将最大的入了 ans，才能保证下次未选取的数一定小于上一次选取的数，例如，1，4，6，8，9，我们先将 9 入 ans，然我们不管在 (6,8) 中选取哪个，那个未被选取的都一定小于 9，接着在 (1,4) 中不管选哪个，那个未被选取的都要比上一个选取的数（6 或 8）小，这就可以保证 A 的合法性。

另外，这个客观的解法需要定义一个三元结构体，分别存储 a, b, pos，在网上看到了一个我没有用过的数据结构来直接搞，十分方便，叫做元组，<tuple>，类似于结构体，十分强大，这里我也提供一下利用元组的解法（代码 Three）。

代码

One：

#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n;
int pos[MAXN];
int a[MAXN], b[MAXN];
ll sumA, sumB;

int main(int argc, char const *argv[])
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", a + i);
        sumA += a[i];
        a[i] <<= 1;
        pos[i] = i;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", b + i);
        sumB += b[i];
        b[i] <<= 1;
    }

    int mid = n / 2 + 1;
    srand((int)time(0));
    while (1)
    {
        ll s1 = 0, s2 = 0;
        random_shuffle(pos , pos + n);
        for (int i = 0; i < mid; i++)
        {
            s1 += a[pos[i]];
            s2 += b[pos[i]];
        }
        if (s1 > sumA && s2 > sumB)
        {
            printf("%d\n%d", mid, pos[0] + 1);
            for (int i = 1; i < mid; i++)
            {
                printf(" %d", pos[i] + 1);
            }
            puts("");
            return 0;
        }
    }

    return 0;
}

Two：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 5;

struct abpos
{
    int a;
    int b;
    int pos;
};

abpos c[MAXN];
vector<int> ans;

int n;
int a[MAXN], b[MAXN];

bool cmp(abpos a, abpos b)
{
    return a.a < b.a;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }

    c[0].a = c[0].b = c[0].pos = 0;
    for (int i = 1; i <= n; i++)
    {
        c[i].a = a[i];
        c[i].b = b[i];
        c[i].pos = i;
    }
    sort(c + 1, c + n + 1, cmp);

    ans.push_back(c[n].pos);

    for (int i = n - 1; i >= 1; i -= 2)
    {
        if (c[i].b > c[i - 1].b)
        {
            ans.push_back(c[i].pos);
        }
        else
        {
            ans.push_back(c[i - 1].pos);
        }
    }

    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << ' ';
    }

    return 0;
}

Three：

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;

typedef tuple<int, int, int> tp;

const int MAXN = 1e5 + 5;

tp tpThree[MAXN];
vector<int> ans;

int n;
int a[MAXN], b[MAXN];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++)
    {
        tpThree[i] = tp(a[i], b[i], i);
    }
    tpThree[0] = tp(0, 0, 0);
    sort(tpThree + 1, tpThree + n + 1);

    int pos;
    tie(ignore, ignore, pos) = tpThree[n];
    ans.push_back(pos);

    int y, y_, pos_;
    for (int i = n - 1; i >= 1; i -= 2)
    {
        tie(ignore, y, pos) = tpThree[i];
        tie(ignore, y_, pos_) = tpThree[i - 1];
        if (y > y_)
        {
            ans.push_back(pos);
        }
        else
        {
            ans.push_back(pos_);
        }
    }

    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << ' ';
    }

    return 0;
}