P8787题解

· · 题解

题目大意

每次操作将序列中相同元素全部写为 \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;
}

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