CF798D 【Mike and distribution】 题解

前言

很妙的思维题。

考察知识点：贪心

难度：三星

题意

给定 两个长度为 ( )的数组，数组中的元素都为正整数，即 。 现在要求你选择出一个下标集合

= {,...} ( ) 。

假设 数组中所有元素和为 , 数组中所有元素和为 ,选出的 集合满足

现在你需要输出一个满足条件的集合 。

思路

想必看完题目大家都知道是贪心了。不用说，这个题目让我们选择最多 个数，而且 都是正整数 ，本着 “不选白不选”的原则，我们直接构造一个大小为 的集合就好了。

题目给定的是 个下标，但是只要求选出的这几个数的和的两倍大于原数组的和。

有蹊跷

不妨考虑先满足 数组的条件，在满足 数组的条件的情况下尽量满足 数组的答案。

首先为了尽量满足 数组的条件，我们先把这两个数组存为一个结构体 ，按照 的大小排序（要记录它们在原数组中的下标）。

肯定是不能单纯的选出前 个的，如果你这么选择你就 了。

这个 的 让人很不爽，于是我们就先选出 这个结构体节点对应在原数组中的下标。

下面称呼结构体中存的 数组就是 , 数组就是 , 下标就是 ;

然后我们现在要在剩下的 个数里面选出 个数，这 个数的和 要 大于等于 原数组的和。

（因为选了第一个，第一个的 ，所以是大于等于）

这时候我们就要想，要选择怎么样的 个呢？

这时候，笔者想了 后发现一个做法：

剩下的所有数里面可以分组考虑，因为是选出 个嘛，也就是两个里面要选出一个来。

不妨把 归为一组 , 归为一组，依此类推。

然后我们惊喜的发现，只要 中任意选一个， 中任意选一个......这样选择下去无论如何一定能够满足 数组的条件。

为什么呢？这种问题的证明实际上只要考虑最坏的情况，也就是最后选择的是:

...(一共选择 个数，这肯定对 来说是最坏的情况)。

这样考虑:

所以， 一定大于 , 能满足数组 的条件。

知道了这个之后，这个题目就豁然开朗了。因为实际上 每一组 我们任意选对 数组的条件都没有影响了。

只要考虑对于 数组是否满足条件就行了。那么我们不妨在每一组里面选出 较大的就行了。

还是因为我们选了 这样子的话, 数组就能保证最后的答案就是合法的了！

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
struct Node {
    int id,dataA,dataB;
    bool operator < (const Node &P) { return P.dataA < dataA; }//重载运算符
} T[MAXN];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch =='-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main() {
    n = read();
    for(int i = 1 ; i <= n ; i ++)
    T[i].dataA = read();
    for(int i = 1 ; i <= n ; i ++)
    T[i].dataB = read(), T[i].id = i;//记得要存放下标
    sort(T + 1 , T + 1 + n);//按照A[i]的从小到大排序
    cout << n / 2 + 1 << endl;
    cout << T[1].id << " ";//先选出第一个
    for(int i = 2 ; i <= n ; i += 2) {
        if(T[i].dataB < T[i + 1].dataB) cout << T[i + 1].id << " ";//每组中哪个 B[i] 大就选哪个
        else cout << T[i].id << " ";
    }
    return 0;
}

总结

对于这种看到 字眼的题目，考虑分组处理。