题解 [email protected]洛谷 | [email protected] 【Settlers' Training】

思路:数据这么小,根据题意模拟即可。


具体做法:

  • 判断第一个数的值,若等于 kk 则进入第四步。
  • 根据题意对每个数遍历进行修改。
  • 回到第一步,直到符合题意为止。
  • 输出统计得到的结果即可。

但是这个程序的正确性依赖于整个过程中的单调不降性质,需要证明:

对于相邻两个数 aabb

  • 如果 a=ba=b,不进行修改, aabb 依然相等。
  • 如果 a<ba\lt b,将 aa 加一,此时 aba\le b

由于初始序列单调不降,因此任意时刻,数列满足单调不降。

程序的正确性得证。


一个小 trick:C++ 中单独的逗号语句的值为最后一个逗号后的表达式的值,与前面无关,因此可以通过这个简写一些代码。


代码:

//By: [email protected]_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;
}