[AGC024C] Sequence Growing Easy 题解

· · 题解

这里提供一种比较新奇的做法。

做这种题首先要特判：如果 x_1>0，那么肯定无解（因为没有 x_0 供给 x_1 变换）。如果相邻两数 a_{i+1}-a_{i}>1，那么也无解——因为题目中说了 x_{i+1} 若要变成非 0 的 a_{i+1}，必须使用操作 x_{i+1}=x_i+1，显然做不到。

特判完就可以开始思考正解。我们先从样例 1 出发。

样例输入 #1：

4
0
1
1
2

该如何操作才能使 x 变为这一串序列呢？

我们先这么操作： x_3=x_2+1=1；

接着：x_2=x_1+1=1；

最后：x_4=x_3+1=2。

可以观察到，当 a_{i+1}-a_i=1 时，我们先变 x_i，再变 x_{i+1} 时就只需一次操作。

但如果 a_{i+1}\le a_i 呢？很显然，x_{i+1} 的变换依赖于 x_i 的变换，x_i 的变换又依赖于 x_{i-1} 的变换……直到扫描到某个 a_j。为满足 x_{i+1}=a_{i+1} 需要先将 x_j 变换为 a_{i+1}-(i-j)-1，然后 x_{j+1}=x_j+1，x_{j+2}=x_{j+1}+1……运用这种思想不断往下递归，一共需要 x_{i+1} 次操作。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,c=0; cin>>n;
  vector<int> v(n);
  for(auto &i:v)cin>>i;
  if(v[0])cout<<"-1\n",exit(0); // 如果第一个数就不为 0 那么肯定无解
  for(int i=1;i<n;i++){
    if(v[i]>v[i-1]+1)cout<<"-1\n",exit(0); // 无解的第二种情况
    c+=v[i]>v[i-1]?1:v[i]; // 分类讨论
  }
  cout<<c<<endl;
  return 0;
}