CF1857B Maximum Rounding

题目大意

给定一个自然数 \(n\)，可以对任意一位进行四舍五入，可以进行任意次，求能得到的最大数。

\(n\) 的长度不超过 \(2\times 10^5\)，没有前导零。

solution

首先，选择四舍五入的数一定 \(\ge 5\)，不然对答案没有贡献。

其次，高位的数可能会受到低位的进位，这启发我们从低位向高位考虑。

由于 \(n\) 很大，所以选择用数组存储。从低位向高位扫一遍，如果当前数加上进位 \(\ge 5\)，那么就对这一位打上标记，并让进位加一。最后如果有进位，先将进位输出，接着从高位扫向低位，若此位有标记，那么从当前位向后应该全输出 \(0\)，否则输出原数接受进位后的结果。

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<bitset>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
int n,m,k;
int A[N];
char s[N];
bitset<N>vis;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		vis.reset();//赋值为0
		scanf("%s",s+1);
		n=strlen(s+1);
		int x=0;
		ROF(i,n,1){
			int t=s[i]-48+x;
			A[i]=t%10;
			x=t/10;
			t=A[i];
			if(t>=5){
				x++;
				vis[i]=1;
			}
		}
		if(x>0) printf("%d",x);
		int f=0;
		FOR(i,1,n) 
		{
			if(vis[i]||f){
				f=1;
				printf("0");
			}
			else printf("%d",A[i]);
		}
		puts("");
	}
	return 0;
}