CF798D 【Mike and distribution】 题解

Mike and distribution

https://ac.nowcoder.com/acm/problem/112024

前言

很妙的思维题。

考察知识点:贪心

难度:三星

题意

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

= {,...} ( ) 。

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

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

思路

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

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

有蹊跷

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

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

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

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

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

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

(因为选了第一个,第一个的 ,所以是大于等于

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

这时候,笔者想了 后发现一个做法:

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

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

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

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

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

这样考虑:

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

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

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

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

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

总结

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

闲人碎语 文章被收录于专栏

刊载算法学习笔记以及一些题解

全部评论

相关推荐

缓解焦虑的最好方法是回家。鼠鼠昨天上午考完了本科阶段的最后一场考试,大概率考得稀烂,但是没多想,考完立马收拾行李,坐上了提前约好的顺风车飞奔回家。虽然家和学校很近,只有一百多公里的路程,但距离上次回家也已经有三四个月了。每次想回家,期间总有考试、毕业设计、面试、实习等等各种各样的原因,没办法回去,待在学校和公司的每一天也都充斥着无形的压力和焦虑。现在终于完成了答辩,考完了试,公司那边也请了假,是时候回去一趟了。没有提前通知爸妈,想给他们一个惊喜。下午提前到了家,他俩还在上班,只好让外公外婆来给我开门。因为我的回家,晚上外婆在厨房格外忙碌,做了满满一大桌子菜,填饱了我天天吃外卖的肚子。晚上也没空...
梦想是成为七海千秋:取决于家庭吧?其实回家更焦虑了,每天起床父母都问实习找好了没简历投递了没今天有没有面试,但是又没有什么结果,玩两下手机父母就会说你看你啥也没找到为什么天天就知道刷手机,怎么不去学习…我现在就希望我能永远在外面实习,报喜不报忧,等拿到一个好offer再回家
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务