【每日一题】Mike and distribution 题解

Description

给一个数组 $c$ ，他的每个数字有两种属性 $a_i$ 和 $b_i$ , 令数组 $c$ 中 $a_i$ 之和为 $sum_a$ , $b_i$ 之和为 $sum_b$
从 $c$ 中取不大于 $\lfloor \frac{n}{2} \rfloor + 1$ 个数字
使得这些数字满足

$2\sum a_i > sum_a$
$2\sum b_i > sum_b$

Solution

很有Codeforces特色的构造题，令 $m = \lfloor \frac{n}{2} \rfloor + 1$ ，注意到不大于 $m$ 个数字可以取
那么我们取 $m$ 个数字一定是最优的
其次，需要针对两倍 $sum$ 的特点，先对 $c$ 数组按 $a$ 的大小排序
先取出第一个元素，随后剩下 $m - 1$ 个元素。
那么剩下 $m - 1$ 个元素两两分组，得到 $(c_2, c_3), (c_4, c_5), \dots, (c_{m - 2}, c_{m - 1})$
那么在两两分组里任取一个元素，我们都能满足 $2\sum a_i > sum_a$
因为最坏情况会取到 $c_1, c_3, \dots c_{m - 2}$ 而显然有， $c_1 \geq c_2, c3 \geq c4, \dots ,c_{m - 2} \geq c_{m - 1}$
最坏条件下仍满足条件，故上述结论得证。
此时，如果我们在两两分组里取 $b_i$ 更大的元素，我们可以满足 $2\sum b_i > sum_b$
因为这样取对于每一组都满足 $b_i >= b_j$ ,加上分离出来的第一个元素，总能满足条件。

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
struct node {
    int a, b, id;
    bool operator < (const node& s) const {
        return a == s.a ? b > s.b : a > s.a;
    }
}c[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[i].a;
        c[i].id = i;
    }
    for(int i = 1; i <= n; i++) {
        cin >> c[i].b;
    }
    sort(c + 1, c + 1 + n);
    vector<int> v;
    v.emplace_back(c[1].id);
    for(int i = 2; i <= n; i += 2) {
        if(c[i].b > c[i + 1].b) {
            v.emplace_back(c[i].id);
        } else {
            v.emplace_back(c[i + 1].id);
        }
    }
    cout << v.size() << '\n';
    for(auto &x : v) {
        cout << x << ' ';
    }
    cout << '\n';
  return 0;
}