郑轻的新生赛今天去打了下   有两道题蛮有意思

差点没做出来。。。。差点丢人了 。。。。。（菜到新生赛都不敢打

J题

这个题 看到有种似曾相识的感觉  也不知道 以前做过没 反正不记得了

思路：

我的思路 我觉得还蛮巧妙的（QAQ）

            柱        
    柱 水 水 水 柱 柱 水 柱  
柱 水 柱 柱 水 柱 柱 柱 柱 柱 柱

 

我们把图以最高的为准，补全。然后统计没放水的地方

首先每一个数代表柱子 都要加上，然后记录一个当前位置之前的最大值 mx。（这个是随着位置更新的）

每到一个位置都比较一下是否大于mx 如果大于  那就 加上( a[ i ] - mx )*( i - 1 )   这是什么东西呢？

看下边的图   比如到第3列的时候  前面最大值就是1 那么我们要加上就是 （2-1）*（3-1）=2

            柱        
加 加 柱 水 水 水 柱 柱 水 柱  
柱 水 柱 柱 水 柱 柱 柱 柱 柱

柱

同样的  当到第7个的时候 我们加上的就是  （3-2）*（7-1）=6  如图

加 加 加 加 加 加 柱        
加 加 柱 水 水 水 柱 柱 水 柱  
柱 水 柱 柱 水 柱 柱 柱 柱 柱

柱

 

这样扫描一遍之后  最高的第七列之前的空位我们就全部加进来了  并且同时把柱子部分也加了

然后我们再倒着扫描一遍 把第七列之后的空位都加上

然后用 整个的格子数  减  我们加出来的格子数    就是答案了

代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll a[maxn];
ll sum;
const int mod=1e9+7;
int main(){
    int n;
    scanf("%d",&n);
    ll mx=-1;
    ll flag=-1;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];//加上柱子
        if(a[i]>mx){
            sum+=(a[i]-mx)*(i-1);//加上空位
            mx=a[i];//更新最大值
        }
        if(flag<a[i])flag=a[i];//记录最高的柱子
    }
    mx=-1;//倒着
    for(int i=n;i>=1;i--){
        if(a[i]>mx){
            sum+=(a[i]-mx)*(n-i);//加上空位
            mx=a[i];//更新最大值
        }
    }
    printf("%lld",flag*n-sum);
}

再放一下赛后给的标程，还没来得及看  也不知道是啥思路

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int l=0,r=n-1;
    int maxl=0,maxr=0;
    long long ans=0;
    while(l<=r)
    {
        if(maxl<maxr)
        {
            maxl=max(maxl,a[l]);
            ans+=max(min(maxl,maxr)-a[l],0);
            l++;
        }
        else
        {
            maxr=max(maxr,a[r]);
            ans+=max(min(maxl,maxr)-a[r],0);
            r--;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

 

H题

思路：

题目提示了说注意化简   那么我们就化简一下

abs(a[j]-a[i])+j-i  如果 a[j]>a[i]    那么式子就是   a[j]-a[i]+j-i  再化简 (a[j]+j)  -  ( a[i]) + i )

                          如果 a[j]<a[i]    那么式子就是   a[i]-a[j]+j-i   也就是 (a[i]-i)  -  (a[j] - i )

那么我们找四个数就ok了 

a[ i ] - i   的最大值和最小值    相减

a[ i ] + i  的最大值和最小值    相减

两个结果取一个最大的就是ans

/*
j-i+a[j]-a[i]--->j+a[j]-(i+a[i])
j-i+a[i]-a[j]--->j-a[j]-(i-a[i])
*/

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int main()
{

    int n;
    scanf("%d",&n);
    int mix1=inf,mix2=inf,maxn=-inf;
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        maxn=max(maxn,i+x-mix1);
        maxn=max(maxn,i-x-mix2);
        mix1=min(mix1,i+x);
        mix2=min(mix2,i-x);
    }
    printf("%d\n",maxn);
    return 0;
}