upc 真假鉴定 思维+模拟
发布日期:2021-09-25 23:57:28 浏览次数:5 分类:技术文章

本文共 1486 字,大约阅读时间需要 4 分钟。

真假鉴定

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有n堆硬币依次排列,每一堆有a_i个。每堆硬币全是真币或全是假币,真币每个重5克,假币每个重4克。你有一台电子天平,可以从每堆硬币中挑出若干个进行一次称量(也可以一个都不选)。现在你想要知道,若要确定前1,2,……,n堆硬币的真假,至少要称量几次。
输入
第一行一个整数n,表示硬币的堆数。
接下来一行n个整数a_i,表示每堆硬币的数量。

输出

n行,每行一个整数,第i行表示想要确定前i堆硬币的真假至少要称量几次。
样例输入 Copy
3
2 3 4
样例输出 Copy
1
1
1
提示

在这里插入图片描述

对于10%的数据,n≤1

对于30%的数据,n≤2
对于60%的数据,n≤100
对于80%的数据,n≤1000
对于100%的数据,n≤10 ^ 5,a_i≤10 ^ 9
存在10%的数据,a_i=1

请教大佬之后,终于搞懂了。

根据给出的提示,可以知道当拿出来的每个组的个数为 1 2 4 8 … 的时候就可以唯一确定,所以问题转换成前 i 个数中1 2 4 8 … 这样组合的最小组数。

思路就是枚举每一个数,找到 <= 当数的最大的2的幂,让这个位置的幂数加1,对当前位置及之前的数,依次枚举1-30(指的是2的幂的位置,比如说 2 ^ 0 的位数为1,2 ^ 3 的位数为4),每种分两种情况讨论:
(1) 当当前的2的幂的个数 > 当前位数与方案数的乘积,说明方案数不够,需要添加方案,添加的方案为 多出来的个数 / 当前位数,当不能整除的时候,还需要多出来一个方案存多余的。
(2)反之则在当前方案后面加上即可。
对于 5 5 5 这种的,显然 5 可以表示成1 2 4 ,往前补位就好了,也就是说每次枚举到的位数,比如当前位数为4,前面需要构成能1 2 4 8 这样的数列,而且每一个数位一定可以放得下,因为枚举的方式是递增的。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int a[N],mp[N];LL fun[N];int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { int t=0; while(a[i]) t++,a[i]/=2; mp[t]++; int ans=0,num=0; for(int j=1;j<=30;j++) { num+=mp[j]; if(num>j*ans) { int tt=num-j*ans; ans+=tt/j; if(tt%j) ans++; } } printf("%d\n",ans); } return 0;}

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/105401511 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Codeforces Eugene and an array
下一篇:玉米田 组合数学 环涂色

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月14日 01时34分43秒