CF718A Efim and Strange Grade 题解
算法
贪心+模拟
思路分析
显然,要最优每一次进位就只能五入不能四舍。而且当我们五入时,要取位数最高的。比如说 \(1.3535\),我们有两种进位方式,一种是进位成 \(1.4\),一种是进位成 \(1.354\),显然前者更优。
那这道题给的次数有啥用呢?
考虑一种“连环进位”。举个例子,\(2.4445\) 最终结果应该是 \(2.5\),进位三次。那我们的代码就很好设计了,先找到位数最高的大于五的数位,然后再向前找连续的 \(4\),连续的个数就是我们达到最优的次数,判断一下和所给的 \(t\) 的大小关系即可。
注意进位时 \(9\) 的再次进位,以及整数位进位会超 long long
等细节问题。
代码
代码仅供参考
#include <bits/stdc++.h>
using namespace std;
namespace Raiden
{
int a = -1, b;
signed work()
{
string s, s1;
int n, t;
cin >> n >> t;
cin >> s;
int st = s.find(".");
for (int i = st + 1; i < s.size(); i++)
{
if (s[i] - '0' >= 5)
{
a = i;
break;
}
}
for (int i = a - 1; i >= st; i--)
{
if (s[i] - '0' == 4)
b++;
else
break;
}
if (a == -1)
cout << s << endl;
else if (a == st + 1)
{
string s1 = s.substr(0, st);
for (int i = st-1; i >= 0; i--)
{
if (s1[i] != '9')
{
s1[i]++;
break;
}
else
s1[i] = '0';
}
if (s1[0] == '0')
cout << 1 << s1 << endl;
else
cout << s1 << endl;
}
else if (t >= b + 1)
{
if (a - b == st + 1)
{
string s1 = s.substr(0, st);
for (int i = st-1; i >= 0; i--)
{
if (s1[i] != '9')
{
s1[i]++;
break;
}
else
s1[i] = '0';
}
if (s1[0] == '0')
cout << 1 << s1 << endl;
else
cout << s1 << endl;
}
else
{
if (s[a - b - 1] == '9')
cout << s.substr(0, a - b - 2) << char(s[a - b - 2] + 1) << '0' << endl;
else
cout << s.substr(0, a - b - 1) << char(s[a - b - 1] + 1) << endl;
}
}
else
{
if (s[a - t] == '9')
cout << s.substr(0, a - t - 1) << char(s[a - t - 1] + 1) << '0' << endl;
else
cout << s.substr(0, a - t) << char(s[a - t] + 1) << endl;
}
return 0;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return Raiden::work();
}
标签:CF718A,题解,s1,++,st,break,int,Strange,进位
From: https://www.cnblogs.com/RyanAdam/p/18336465