upc 真假鉴定 思维+模拟

真假鉴定
时间限制: 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<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#define X first
#define Y second
using namespace std;

typedef long long LL;
typedef pair<int,int> 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;
}