积木大赛 noip2013提高组day2

这道题一开始想到处理中间是0的位置，但这样时间太慢了，后来想到一种类似二分的方法，就是把这一段的最小值找到，全部减去最小值，然后有0一出现，就又递归处理前一段，每次答案就加上这一段的最小值；

AC代码

 #include<iostream>

 #include<cstdio>

 #define maxx 100005

 using namespace std;

 int n;

 int block[maxx];

 long long ans;

 void go(int l,int r)

 {

     if(l>r)return;

     if(l==r){ans+=block[l];block[l]=;return;}

     int pos;

     int minn=maxx;

     for(int i=l;i<=r;i++){

         if(block[i]<minn)

         {

             minn=block[i];

             pos=i;

         }

     }

     ans+=minn;

     for(int i=l;i<=r;i++)

         block[i]-=minn;

     go(l,pos-);

     go(pos+,r);

 }

 int main()

 {

     freopen("block.in","r",stdin);

     freopen("block.out","w",stdout);

     cin>>n;

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

     scanf("%d",block+i);

     go(,n);

     cout<<ans;

     return ;

 }

但有个新高一的介绍了一种超厉害的方法，输入完就处理完了，每一步如果hi小于hi-1就加上差值，最后答案就是差值的和时间O（n）

AC代码

 #include<iostream>

 #include<cstdio>

 #define maxx 100005

 using namespace std;

 int n;

 int block[maxx];

 long long ans;

 int main()

 {

     freopen("block.in","r",stdin);

     freopen("block.out","w",stdout);

     cin>>n;

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

     {

         scanf("%d",block+i);

         if(block[i]>block[i-])

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

     }

     cout<<ans;

     return ;

 }

巴特西

积木大赛 noip2013提高组day2

最新文章

热门文章