题解 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;
}
```