首页 > 其他分享 >【题解】拆分

【题解】拆分

时间:2024-08-30 20:38:54浏览次数:9  
标签:测试点 int 题解 样例 ai 拆分 集合 mex

题目描述

【题目描述】
    鸡尾酒又带着大家学习新定义啦!今天要学习的内容是集合的 mex,集合的 mex 指的是一个集合没有出现过的最小自然数。
    例如,mex({1,2}) = 0、mex({0,1,2,3}) = 4。
    现在你有一个包含 n 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的 mex 值之和最大,求这个最大值是多少。
【输入格式】
    第一行输入一行一个正整数 n,接下来一行包含 n 个非负整数,表示集合中的元素 ai。
【输出格式】
    输出一行一个整数表示答案。
【样例】
    样例输入1
        5
        0 0 1 1 2
    样例输出1
        5
    样例说明1
        分成两个集合 {0, 1}, {0, 1, 2},第一个集合的 mex 为 2,第二个集合的 mex 为 3 ,两个集合的 mex 之和为 5 ,这样分集合是最大的。
        当然也可以分成 {0}, {0}, {1}, {1}, {2},但是这样五个集合的 mex 之和为1 + 1 + 0 + 0 + 0 = 2。
    样例输入2
        5
        1 2 3 4 5
    样例输出2
    0
    样例说明2
        因为原集合没有 0,所以无论怎么分集合,每一个新集合都不会有 0,所以每一 个集合的 mex 都为 0,答案一定为 0。
【数据范围】
    本题共有 10 个测试点 第一个测试点有 0 < ai 第二个测试点有 ai = 0
    第 3 − 4 个测试点有 0 ≤ ai ≤ 1
    对于所有测试点,有 1 ≤ n ≤ 105, 0 ≤ ai ≤ 1000

题目大意

给定一个包含 \(n\) 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的 \(mex\) 值之和最大,求这个最大值是多少。

关于 \(mex\) 值的定义:一个集合中没有出现过的最小自然数

思路

该题主要考察:贪心

众所周知,集合内是没有相同元素的。因此可以将每个分割后的新集合分类讨论:

  1. 集合中有 \(0\):此时需要计算集合的 \(mex\) 值。
  2. 集合中没有 \(0\):此时集合的 \(mex\) 值为 \(0\)。

所以,对于每一个 \(0\) 就会有对应的一个新集合。

然后,由于题目要求所有新集合的最大的 \(mex\) 值之和,所以每个新集合都要尽量有更多的元素。
但是,考虑特殊情况:对于集合 \(\{0, 1, 2, ..., 999, 1000\}\) 来说,其 \(mex\) 值为 1001。
所以要判定特殊情况。

那么,题目就迎刃而解了。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, INF = 0x3f3f3f3f;
int n, a[N];
int t[N];

int main()
{
    scanf("%d", &n);

    int cnt = 0; // cnt 用于 统计新集合个数
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        if (a[i] == 0) cnt ++ ; // 对于每一个 0 就会有对应的一个新集合
        else t[a[i]] ++ ;
    }

    int ans = 0;
    while (cnt -- ) // 依次处理每个新集合
    {
        // 注意 i <= 1001,应对集合为 {0, 1, 2, ..., 1000} 的情况
        for (int i = 1; i <= 1001; i ++ )
        {
            if (t[i]) t[i] -- ;
            else
            {
                ans += i;
                break;
            }
        }
    }
    printf("%d\n", ans);

    return 0;
}

标签:测试点,int,题解,样例,ai,拆分,集合,mex
From: https://www.cnblogs.com/T-hong/p/18389414

相关文章

  • 题解:CF916D Jamie and To-do List
    题意维护一个数据结构,支持以下几种操作:setaixi:设置任务\(a_i\)的优先级为\(x_i\),如果该列表中没有出现则加入该任务。removea_i:删除该任务。querya_i:求优先级比\(a_i\)小的任务个数,如果没有则输出\(-1\)。undosum:删除此次操作之前的\(sum\)次操作。分析前......
  • 题解:CF916B Jamie and Binary Sequence (changed after round)
    题意把一个数分解成恰好\(k\)个\(2^{a_i}\)次方的和,可以重复,要求保证最大的\(a_i\)要尽可能的小时,\(a\)的字典序尽可能大,输出序列\(a\)。分析首先我们借助二进制拆出一个满足\(n=\sum2^{a_i}\)序列\(a\),满足\(a\)的长度最小。若此时\(a\)的长度大于\(k\),显......
  • 题解:CF914C Travelling Salesman and Special Numbers
    题意定义\(\operatorname{popcount}(x)\)为\(x\)二进制下\(1\)的个数。定义对\(x\)的一次操作:\(x\gets\operatorname{popcount}(x)\),显然任意正整数经过若干次操作后会变为\(1\)。给定\(n\)和\(k\),其中\(n\)是在二进制下被给出,求出所有不大于\(n\)且将其变为......
  • 题解:CF915G Coprime Arrays
    题意我们称一个大小为\(n\)的数组\(a\)互质,当且仅当\(\gcd(a_1,a_2,\cdots,a_n)=1\)。给定\(n,k\),对于每个\(i\)\((1\lei\lek)\),你都需要确定这样的数组的个数——长度为\(n\)的互质数组\(a\),满足对每个\(j\)\((1\lej\len)\),都有\(1\lea_j\lei\)。分析......
  • [COCI2012-2013#2] INFORMACIJE 题解
    前言题目链接:洛谷。题意简述你需要构造一个\(1\simn\)的排列\(a\),满足\(m\)个条件,格式如下:1xyv:\(\max\limits_{i=l}^ra_i=v\)。2xyv:\(\min\limits_{i=l}^ra_i=v\)。题目分析首先这个最值很难受,考虑能不能转化成我们喜欢的二元关系......
  • Luogu P10997 Partition 题解 [ 蓝 ] [ 轮廓 dp ]
    Partition:一道dp神题,用到了以轮廓线的轨迹来做dp的技巧,和敲砖块这题的状态设计有点相似。观察首先观察样例,发现整张图可以看作是被两条线分隔开的。同时每个颜色的四个方向上又存在一大堆奇怪的性质,很容易发现这两条线一条是从左上到右下的线,另一条是从右下到左上的线。暴......
  • CF603E 题解
    题意给定一个\(n\)个结点的无向图,初始没有边。接下来有\(m\)个询问,每次向图中加入一条连接\((u,v)\)权值为\(w\)的边。每次加边后,查询是否存在一个边集\(E\),满足当图中只有\(E\)中的边时,所有点的度数均为奇数。同时你还要最小化\(\max\limits_{(u,v,w)\inE}......
  • 【Mysql】mysql count主键字段很慢超时 执行计划Select tables optimized away ,最终调
     背景: mysql表 主键字段count,速度很慢,耗时将近30s   从执行计划可以看出:explainSELECTCOUNT(rule_id)ASdataCountFROM`sku_safe_stock_rule`;   原理分析:SelecttablesoptimizedawaySELECT操作已经优化到不能再优化了(MySQL根本没有遍历......
  • CF891E Lust 题解
    题目链接点击打开链接题目解法会不了\(egf\)/ll我们把贡献变成\(\prod\limits_{j\neqi}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n(a_i-[i=j])\)即答案为一开始的乘积\(-\)\(k\)次操作之后所有数乘积的期望因为有顺序,所以用\(egf\)的形式表示最后乘积的期......
  • UVA12421 (Jiandan) Mua (I) - Lexical Analyzer题解
    没什么废话、超级珂爱的大模拟。本蒟蒻写了2h才过。其实就是按题意模拟即可,不需要什么高深的算法。本人就是错在了符号中的“=”,因为如果是连续的两个等于号,只能输出“==”,而不能输出“=”“==”,然后本人就卡在这个地方卡了1.5h。代码量也不大,主要是毒瘤细节模拟题。......