自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:42:28，当前版本为作者最后更新于2023-07-07 15:11:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

每次操作将序列中相同元素全部写为 $\sqrt{\left \lfloor\frac{h_i}{2}\right\rfloor -1}$，问几次操作能将序列中所有元素置成一。

题目解析

本题是一道贪心。

使用两个数组，一个存储竹子高度，一个存储竹子还能被砍几次。

循环砍伐可以砍伐次数最高的竹子，直到竹子都不能被砍。

代码如下：

#include<bits/stdc++.h>
const int maxn=1000050;
using namespace std;
int main(){
	int h[maxn],cnt[maxn],n,ans=-1,num=0;cin>>n;
    for(int i=0;i<n;++i){
    	cin>>h[i];
    	int temp=h[i];
    	while(temp-1)
    		cnt[i]+=1,temp=sqrtl(temp/2+1);
		ans=max(ans,cnt[i]);
	}
	for(int i=ans;i>0;--i)
		for(int j=0;j<n;++j)
			if(cnt[j]==i){
				if(h[j]!=h[j+1])
					num+=1;
				cnt[j]-=1;h[j]=sqrtl(h[j]/2+1);
			}
	cout<<num;
	return 0;
}

可结果却不尽人意：

我思考良久后，发现了一个问题：

没开 long long!

正如网络所说：10 年 OI 一场空，不开 long long 见祖宗。

正确代码如下：

#include<bits/stdc++.h>
const long long maxn=1000050;
using namespace std;
int main(){
	long long h[maxn],cnt[maxn],n,ans=-1,num=0;cin>>n;
    for(long long i=0;i<n;++i){
    	cin>>h[i];
    	long long temp=h[i];
    	while(temp-1)
    		cnt[i]+=1,temp=sqrtl(temp/2+1);
		ans=max(ans,cnt[i]);
	}
	for(long long i=ans;i>0;--i)
		for(long long j=0;j<n;++j)
			if(cnt[j]==i){
				if(h[j]!=h[j+1])
					num+=1;
				cnt[j]-=1;h[j]=sqrtl(h[j]/2+1);
			}
	cout<<num;
	return 0;
}

都看到这里了，留个赞再走吧。