2021-01-12 10:42 已编辑牛客运营

关注

【每日一题】1月12日题目精讲

题号 NC112024
名称 Mike and distribution
来源 CF798D
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者 YangYL°

前言

很妙的思维题。

考察知识点：贪心

难度：三星

题意

给定 $A,B$ 两个长度为 $n$ ( $n <= 10 ^ 5$ )的数组，数组中的元素都为正整数，即 $1 <= A_i,B_i <= 10 ^ 9$ 。现在要求你选择出一个下标集合

$P$ = { $p_1,p_2$ ,... $p_{k}$ } ( $k <= n / 2 + 1$ ) 。

假设 $A$ 数组中所有元素和为 $sumA$ , $B$ 数组中所有元素和为 $sumB$ ,选出的 $P$ 集合满足

$\sum_{p_i ∈ P}{A_{p_i}} * 2 > sumA$
$\sum_{p_i ∈ P}{B_{p_i}} * 2 > sumB$

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

思路

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

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

~~有蹊跷~~

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

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

肯定是不能单纯的选出前 $n / 2 + 1$ 个的，如果你这么选择你就 $too$ $young$ $too$ $simple$ 了。

这个 $n / 2 + 1$ 的 $+ 1$ 让人很不爽，于是我们就先选出 $T[1]$ 这个结构体节点对应在原数组中的下标。

下面称呼结构体中存的 $A$ 数组就是 $T[i].A$ , $B$ 数组就是 $T[i].B$ , 下标就是 $T[i].id$ ;

然后我们现在要在剩下的 $n - 1$ 个数里面选出 $n / 2$ 个数，这 $n / 2$ 个数的和 $* 2$ 要 大于等于 原数组的和。

（因为选了第一个，第一个的 $1 <= A_i,B_i$ ，所以是大于等于）

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

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

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

不妨把 $T[2],T[3]$ 归为一组 , $T[4],T[5]$ 归为一组，依此类推。

然后我们惊喜的发现，只要 $T[2],T[3]$ 中任意选一个， $T[4],T[5]$ 中任意选一个......这样选择下去无论如何一定能够满足 $A$ 数组的条件。

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

$T[1],T[3],T[5],T[7]$ ...(一共选择 $n / 2 + 1$ 个数，这肯定对 $A$ 来说是最坏的情况)。

这样考虑: $T[1].A >= T[2].A , T[3].A >= T[4].A , T[5].A >= T[6].A......$

所以， $\sum{T[i].A}$ $* 2$ 一定大于 $sumA$ , 能满足数组 $A$ 的条件。

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

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

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

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