竞赛讨论区 > 【每日一题】1月12日题目精讲

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

头像
王清楚
编辑于 2021-01-12 10:42:29 APP内打开
赞 5 | 收藏 0 | 回复7 | 浏览494

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

图片说明

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

题解

作者 YangYL°

前言

很妙的思维题。

考察知识点:贪心

难度:三星

题意

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

= {,...} ( ) 。

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

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

思路

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

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

有蹊跷

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

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

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

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

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

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

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

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

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

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

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

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

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

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

这样考虑:

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

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

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

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

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

总结

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

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目1月19日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

7条回帖

回帖
加载中...
话题 回帖

本文相关内容

近期热帖

等你来战

查看全部

热门推荐