P1969积木大赛

这是2018与2013提高组的真题，可怕，，原题出了两年，是个纯模拟。

读完题后就想写一个朴素的模拟，先遍历层数，再把达到层数的宽度#存起来，再判断是否连续，如果不连续ans++，然后每一次循环都要初始化，所以第一次提交得了80pts,TLE了最后两个点。然后再去看题解，竟然发现：当i+1组数据大于i组数据，ans+=h[i+1]-h[i]，因为只要小于就是前面的最大的操作数，然后因为不连续所以即使大于前面的但小于前面最大ans也需要++。

1.思路清晰，对时间复杂度进行计算，10^5for来for去再加memset一般就超时了

2.模拟题还是需要找找性质，找到最优的解题方法，简单的题要追求满分

代码1（80‘）：

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define N 10000005

 using namespace std;

 int n;

 int h[N],biuld[N];

 int max_h=-;;

 int ans=;

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&h[i]);

         max_h=max(h[i],max_h);

     }

     for(int i=;i<=max_h;i++){

         int cnt=;

         memset(biuld,,sizeof(n+));

         for(int j=;j<=n;j++){

             if(h[j]>=i){//假如还需要加高度

                 biuld[++cnt]=j;//存储第几个

                 //cout<<biuld[cnt]<<endl;

             }

         }

     //    cout<<endl;

         ans++;

         for(int i=;i<=cnt-;i++){//判断需要几次操作

             if(biuld[i+]-biuld[i]>=){//假如不是相邻的

                 ans++;

             }

         }

     }

     cout<<ans;

     return ;

 }

代码2（100’）：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n,ans=;

 int h[];

 int main(){

     cin>>n;

     h[]=;

     for(int i=;i<=n;i++){

         cin>>h[i];

         if(h[i]>h[i-]){//假如后面的比前面的要小

             ans+=h[i]-h[i-];

         }

     }

     cout<<ans;

     return ;

 }

巴特西

P1969积木大赛

最新文章

热门文章