CF610B Vika and Squares 题解

· · 题解

思路：

一句话总结：让两桶最少的油漆距离尽可能的远。

我们将原来 a 的序列在后面复制一份，这样所有的情况就会在一个数组里呈现出来，例如样例 1：

5
2 4 2 3 3

将 a 数组复制一份得：

2 4 2 3 3 2 4 2 3 3

这样最优解就会是：

2 4 2 | 3 3 2 4 2 | 3 3

我们把 a 数组中最小的数，记作 minn。然后遍历一遍复制后的 a 数组中两个最小值之间的间隔最大值，记作 maxn。

那我们就可以找到规律：

  1. Vika 最少可以涂 n \times minn 个正方形；
  2. 最优解一定是 n \times minn+maxn。

那么就得出，最后答案是 n \times minn+maxn。

当然，如果 a 数组中数据相同时，答案为 n \times minn。

AC 代码如下：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long int n,a[400005],minn=1e9+9,sum;
bool xt=true;
inline long long int read()
{
    long long int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-48;ch=getchar();}
    return s*w;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        if(i!=1)
        {
            if(a[i]!=a[i-1])
              xt=false;
        }
        minn=min(a[i],minn);
    }
    if(xt==true)
    {
        cout<<n*minn;
        return 0;
    }
    sum+=n*minn;
    for(int i=n+1;i<=2*n;i++)
        a[i]=a[i-n];
    int l=-1,maxn=-1;
    for(int i=1;i<=2*n;i++)
    {
        if(a[i]==minn)
        {
            if(l==-1)
                l=i;
            else
            {
                maxn=max(i-l-1,maxn);
                l=i;
            }
        }
    }
    cout<<sum+maxn;
}