算法
很容易发现转化为差分数组之后
转化为 把 第 \(2\) ~ \(n\) 位的数字变为 \(0\)
显然需要的时间即为( \(X\) 为正数的和, \(Y\) 为负数绝对值的和)
\(max(X, Y)\)
很显然最终的数组决定在差分数组的第 \(1\) 位
这里我没有想到
最后的数列只能和 第 \(1\) 位和第 \(n + 1\) 位 \(\pm 1\)
因此可能性即为( \(X\) 为正数的和, \(Y\) 为负数绝对值的和)
\(max(X, Y) - min(X, Y)\)
代码
#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e5 + 20;int n;
int Num[MAXN], Dif[MAXN];int Pos_Sum = 0, Neg_Sum = 0;
void calc()
{for (int i = 2; i <= n; i++){if(Dif[i] > 0)Pos_Sum += abs(Dif[i]);elseNeg_Sum += abs(Dif[i]);}
}void solve()
{calc();int Time = std::max(Pos_Sum, Neg_Sum);int Type = Time - std::min(Pos_Sum, Neg_Sum) + 1;printf("%lld\n%lld", Time, Type);
}signed main()
{scanf("%lld", &n);for (int i = 1; i <= n; i++){scanf("%lld", &Num[i]);Dif[i] = Num[i] - Num[i - 1];}solve();return 0;
}
总结
注意差分数组的性质包含了 \(1\) ~ \(n + 1\)
