CF1857B Maximum Rounding 题解

题面

题目大意

给定 \(T\) 组数据，每组数据一个自然数 \(n\)，可以多次选择第 \(k\) 位数进行四舍五入，求出四舍五入后该数的最大值。

分析思路

思想：贪心。

这里给定了两种操作。四舍和五入。显然我们想要让最终的结果最大，我们的操作只能进行五入而不可以进行四舍。因为如果我们进行了四舍，第 \(k\) 位如果小于等于 \(4\)，那么这一位将要变成 \(0\)，相对于原数反而变小了，这显然不是我们想要的结果。

代码实现

为了方便进位的操作，我们用字符数组来存储输入的数字，再将数组反转过来转换到整型数组。然后对数组进行一次遍历，若当前数位上的数大于或等于 \(5\)，就将下一位的数 \(+1\)，表示进了一位。我们再用一个变量 \(maxx\) 记录当前可以进位的最高位，\(maxx\) 初始为 \(-1\)。

我们经过观察可以发现：若一个数有进位，那么最高进位的那一位上所有前面的位数都是不变的，后面的位数都是等于 \(0\) 的。例如：\(419860\)，最高进位数为 \(k=4\) 那么第五位 \(4\) 不变，最高进位的数 \(+1\) 等于 \(2\)，后面的数全部为 \(0\)，所以最终的结果为 \(420000\)，那么我们的代码也可以模拟这种方式进行书写。

我们这里分四种情况讨论。

\(\bullet\) 当这个数一位都没有进位时（即遍历完后 \(maxx\) 仍然等于 \(-1\)），直接输出原数。

\(\bullet\) 当这个数的进位在最高位上且最高位之前是 \(9\)，现在又进了一位时。

\(\bullet\) 当这个数的进位在最高位上且最高位没有再进位时。
（理论上来说第二种和第三种差别不大，都是输出最高位然后后面补 \(0\)，但代码上稍微有点出入，请看下面的代码。）

\(\bullet\) 当这个数的进位在中间的位数时。进位的位数前面的所有数按原数输出，后面的所有数补 \(0\) 即可。

核心代码：

cin >> s;
int len = s.length();
for (int i = 0;i <= len - 1;i++){ //将字符串翻转过来存入整型数组 。 
	arr[i] = s[len - i - 1] - '0';
}
int maxx = -1;
for (int i = 0;i <= len - 1;i++){ //遍历数组，寻找可以五入的位数。 
	if (arr[i] >= 5){
		arr[i + 1]++; //如果当前位数大于等于5，那么五入，即下一位 +1。 
		maxx = i + 1; //更新最高进位的位数。 
	} 
}
if (maxx == -1){ //第一种情况。 
	for (int i = 0;i <= len - 1;i++){
		printf("%lld",arr[len - i - 1]);
	} 
	printf("\n");
}
else if (maxx == len){ //第二种情况。 
	printf("%lld",arr[maxx]);
	for (int i = 0;i <= len - 1;i++){
		printf("0");
	}
	printf("\n");
}
else if (maxx == len - 1){ //第三种情况。 
	printf("%lld",arr[maxx]);
	for (int i = 0;i <= len - 2;i++){
		printf("0");
	}
	printf("\n");
}
else { //第四种情况。 
	for (int i = 0;i <= len - maxx - 2;i++){
		printf("%lld",arr[len - i - 1]);
	}
	printf("%lld",arr[maxx]);
	for (int i = 0;i <= len - (len - maxx - 2) - 3;i++){
		printf("0");
	}
	printf("\n");
}

此题难度大约在 普及- 左右。