题解 CF63B 【Settlers' Training】
rui_er
2020-09-03 17:07:50
思路：数据这么小，根据题意模拟即可。
---
具体做法：
- 判断第一个数的值，若等于 $k$ 则进入第四步。
- 根据题意对每个数遍历进行修改。
- 回到第一步，直到符合题意为止。
- 输出统计得到的结果即可。
但是这个程序的正确性依赖于整个过程中的单调不降性质，需要证明：
对于相邻两个数 $a$ 和 $b$：
- 如果 $a=b$，不进行修改， $a$ 与 $b$ 依然相等。
- 如果 $a\lt b$，将 $a$ 加一，此时 $a\le b$。
由于初始序列单调不降，因此任意时刻，数列满足单调不降。
程序的正确性得证。
---
一个小 trick：C++ 中单独的逗号语句的值为最后一个逗号后的表达式的值，与前面无关，因此可以通过这个简写一些代码。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k, a[N], ans;
int main() {
scanf("%d%d", &n, &k);
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
do {
if(a[1] == k) return printf("%d\n", ans), 0;
for(int i=1;i<=n;i++) {
if(a[i] < k && a[i] != a[i+1]) ++a[i];
}
}while(++ans, true);
return 0;
}
```