https://www.cnblogs.com/violet-acmer/p/9739115.html
题意:
找到最小的包含子序列a的序列s,并且序列s是 p -莫干山序列。
题解:
很容易想到 p = max_ai+1,并且a[1]对应着s[1],不然需要在a[1]前加其他数来使的a[1]->某s[i],肯定比不加的序列要长。
遍历a[ ] 数组,分三种情况讨论
①a[i] > a[i-1]
此种情况下,a[i-1]--a[i]在s中是连续的一段序列,res += a[i]-a[i-1]。
②a[i] < a[i-1]
这种条件对应的情况为 a[i-1] -> p -> a[i] ,res += p-a[i-1]+a[i]。
③a[i] == a[i-1]
相等的话,正好相差一个周期,res += p 。
注意结果要用 long long 型。
AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int maxn=2e5+; int a[maxn]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i <= n;++i)
scanf("%d",a+i);
ll res=;
int p=;
for(int i=;i <= n;++i)
p=max(p,a[i]);
p++;
for(int i=;i <= n;++i)
{
if(a[i] > a[i-])
res += a[i]-a[i-];
else if(a[i] < a[i-])
{
int k=a[i-]/p;
res += ((k+)*p-a[i-])+a[i];
}
else
res += p;
}
printf("%lld\n",res);
}