Test 6.24 T2 集合

拼搏现实的明天。 2021-11-23 15:52 175阅读 0赞

## 问题描述 ##

有一个可重集合,一开始只有一个元素 0。  
你可以进行若干轮操作,每轮你需要对集合中每个元素 x 执行以下三种操作之一:

1.  将 x 变为 x+1;
2.  选择两个非负整数 y,z 满足 y+z=x ,将 x 变为这两个元素;
3.  什么都不做。

给出一个最终的集合,求至少经过几轮才能得到这个集合。

## 输入格式 ##

第一行一个正整数 n,表示最终集合的大小。  
第二行 n 个非负整数 ai,表示最终集合中的元素。

## 输出格式 ##

输出一个整数,表示答案。

## 样例输入 ##

5  
0 0 0 3 3

## 样例输出 ##

５

## 解析 ##

不妨倒过来思考，考虑如何通过将一个数减一和合并两个数使目标集合变成只有0的集合。对于任意两个数\\(a\\)和\\(b\\)，如果将两个数分开减为0再合并，那么操作次数为\\(max(a,b)+1\\)，而先合并再减小为0的操作次数为\\(a+b+1\\)。显然第一种更优。推广开来，我们的最优策略即为每轮先和并所有的0，再把不是0的减1，直到只剩一个0为止。

具体实现也很简单。每次把0的数量减半，同时减小长度。预处理每个数在哪一轮会减为0，并在那一轮最后加上新的0的个数。

## 代码 ##

#include <iostream> #include <cstdio> #include <algorithm> #define N 1000002 using namespace std; int n,i,a[N],cnt[N],num,ans; int main() { freopen("set.in","r",stdin); freopen("set.out","w",stdout); cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) cnt[a[i]]++; num=cnt[0]; while(n>1){ ans++; n-=num/2; num=(num+1)/2; num+=cnt[ans]; } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }

转载于:https://www.cnblogs.com/LSlzf/p/11079005.html

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关 [BJDCTF 2nd]test

ssh ctf@node3.buuoj.cn -p <port> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sh

浅浅的花香味﹌/ 2023年02月20日 04:52/ 0 赞/ 10 阅读

相关求a100的值,an是一个集合{2^s+2^t且t＞s＞=0}程序验证

求a100的值,an是一个集合\{2s+2t且t>s>=0\}程序验证输出结果为：a100(14.0,8.0)=16640.0 an(t,s)=v Hell

我会带着你远行/ 2022年11月15日 14:22/ 0 赞/ 103 阅读

相关 624-VS2019创建工程项目

VS2019创建工程项目创建单工程项目 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50

心已赠人/ 2022年09月12日 04:55/ 0 赞/ 228 阅读

相关 FAILED: InvalidConfigurationException hive.server2.authentication can't be none in non-testing mode

在cloudera manager里面配置hive + sentry 启动hiveserver2 执行命令 show roles 报错： Caused by

绝地灬酷狼/ 2022年07月24日 12:02/ 0 赞/ 98 阅读

相关 [leetcode]: 624. Maximum Distance in Arrays

1.题目 Given m arrays, and each array is sorted in ascending order. Now you can pick up

野性酷女/ 2022年06月14日 10:56/ 0 赞/ 107 阅读

相关 CD UVA - 624 ————01背包（寻找路径）

You have a long drive by car ahead. You have a tape recorder, but unfortunately your bes

客官°小女子只卖身不卖艺/ 2022年05月17日 05:47/ 0 赞/ 166 阅读

相关 at&t 位测试（test）

TEST 指令最常见的用途是检查EFLAGES寄存器的标志位 .section .data output_cpuid: .asciz "T

心已赠人/ 2022年04月22日 11:00/ 0 赞/ 183 阅读

相关 2019多校联讯 test 3 T2

![1596060-20190609191922509-1700475750.png][] ![1596060-20190609191947477-1717671360.pn

曾经终败给现在/ 2021年12月23日 23:57/ 0 赞/ 145 阅读

相关 Test 6.24 T2 集合

问题描述有一个可重集合,一开始只有一个元素 0。你可以进行若干轮操作,每轮你需要对集合中每个元素 x 执行以下三种操作之一: 1. 将 x 变为 x+1; 2

拼搏现实的明天。/ 2021年11月23日 15:52/ 0 赞/ 176 阅读

相关 SRX_Test_2_key

转载自 Livedream YBT1396 include<iostream> include<map> include<queue> i

╰+攻爆jí腚メ/ 2021年10月25日 14:56/ 0 赞/ 153 阅读