【每日一题】Mike and distribution 题解

Description

给一个数组 ，他的每个数字有两种属性 和 , 令数组 中 之和为 , 之和为
从 中取不大于 个数字
使得这些数字满足

Solution

很有Codeforces特色的构造题，令 ，注意到不大于 个数字可以取
那么我们取 个数字一定是最优的
其次，需要针对两倍 的特点，先对 数组按 的大小排序
先取出第一个元素，随后剩下 个元素。
那么剩下 个元素两两分组，得到
那么在两两分组里任取一个元素，我们都能满足
因为最坏情况会取到 而显然有，
最坏条件下仍满足条件，故上述结论得证。
此时，如果我们在两两分组里取 更大的元素，我们可以满足
因为这样取对于每一组都满足 ,加上分离出来的第一个元素，总能满足条件。

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;
}