CF718A解题报告

CF718A 解题报告

题意

给你一个长度为 \(n\) 的浮点数，最多四舍五入 \(t\) 次，求可以得到的最大值。

注意：

• 四舍五入之针对小数部分，不针对整数部分。
• 输出时不能有前缀 \(0\)，和后缀 \(0\)。
• 当最大的数变成整数了，就不输出小数点。

分析

根据题面，很容易想到要用贪心，只需要再加那么一点的模拟就好了。

贪心的思路非常简单，我们发现当一个数四舍五入后，它后面的数都会变成 \(0\)，所以我们可以选择尽可能靠左的位置进行四舍五入，使得最终结果最大。

先找到第一个可以四舍五入的位置，即在小数点之后且大于等于 \(5\) 的数；然后模拟每一次进位，在过程中特判一下是否小数部分全没了，如果没了就向整数部分进位。

输出的时候再特判一下小数点是否在最后一位，最后输出就好了。

优化：在处理四舍五入进位的时候可以不用实时的 erase 可以直接将 \(n\) 减去 \(1\) 来实现缩短长度的效果，输出的时候使用 substr 进行输出就好了。

代码

#include<bits/stdc++.h>
using namespace std;

int n, t, cnt;
string s;

int main(){
	cin >> n >> t >> s;
	while (cnt < n && s[cnt] != '.') cnt++;
	while (cnt < n && s[cnt] < '5') cnt++;//求出最靠左的可以四舍五入的位置
	if (cnt == n){//特判如果都不能四舍五入
		cout << s;
		return 0;
	}
	while (t > 0 && s[cnt] >= '5'){//当能四舍五入的时候
		n = cnt--;
		if (s[cnt] == '.'){//特判小数部分取完了
			s[--cnt]++;
			while (cnt > 0 && s[cnt] > '9') s[cnt] = '0', s[--cnt]++;//向整数位进位
			if (cnt == 0 && s[cnt] > '9') s = "10" + s.substr(1, n);//特判最高位进位
			break;
		}
		t--, s[cnt]++;
	}
	if (s[n-1] == '.') n--;//特判如果没有小数部分了
	cout << s.substr(0,n);
	return 0;
}