洛谷题面

较为简单，但还是因为细节问题挂了几发。

题目大意

有 \(n\) 个数 \(w_1,w_2,\cdots,w_{n-1},w_n\)，若有 \(k\) 个 \(w\) 值满足存在一个数 \(x\) 使得 \(2^x\) 为这 \(k\) 个 \(2^w\) 的和，则这一组合是合法的，我们希望找到最小的组数 \(m\)，使这 \(n\) 个 \(w\) 组成 \(m\) 个合法组合。

给出 \(n\) 和 \(w_i\)，输出最小的 \(m\)。

题目分析

我们可以一步一步从低次幂向高次幂合并，\(k(k=2r \texttt{且 r 为整数})\) 个 \(2^x\) 可以合并为 \(\dfrac{k}{2}\) 个 \(2^{x+1}\)。

思路就出来了：

我们用一个桶 \(t_x\) 来记录每个数值 \(x\) 的个数。

但是如何记录答案呢？

我们发现上面只讨论了 \(k\) 为偶数的情况，所以若 \(k\) 为奇数，则取出 \(\left\lfloor\dfrac{k}{2}\right\rfloor\) 个 \(2^x\)，剩下的 \(1\) 个则保留。

坑点：

• 因为更新是 \(t[i+1]\gets t[i+1]+\dfrac{t[i]}{2}\)，所以可能会一直向上迭代更新，边界不一定是 \(i\le \max_w\)。

• 桶的大小要开到 \(10^6+50\)，我最初习惯性开成了 \(10^6+5\)，会 \(\frak{Wrong~Answer~On~Test~36}\)。

这是因为我们在向上时迭代时可能会不停向上更新，开到这儿就合适了。

代码

//2022/1/5const int ma=1e6+50;

int t[ma]; 

int n;

int ans,maxx;

int main(void)
{
	n=read();
	
	for(register int i=1;i<=n;i++)
	{
		int x=read();
		
		t[x]++;
		
		maxx=max(maxx,x);
	}
	
	for(register int i=0;i<=maxx || t[i]!=0;i++)
	{
		if(t[i]!=0)
		{
			t[i+1]+=t[i]/2;
			
			if(t[i]%2==1)
			{
				ans++;
			}
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}