EOJ2018.10 月赛(B 数学+思维题)

传送门:Problem B

https://www.cnblogs.com/violet-acmer/p/9739115.html

题意:

  找到最小的包含子序列a的序列s,并且序列s是 pEOJ2018.10 月赛(B 数学+思维题) -莫干山序列。

题解:

  很容易想到 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);
}
上一篇:iOS 定时器 NSTimer、CADisplayLink、GCD3种方式的实现


下一篇:【数学 思维题】HDU4473Exam