首页 > 其他分享 >题解:CF718A Efim and Strange Grade

题解:CF718A Efim and Strange Grade

时间:2024-08-01 13:17:57浏览次数:14  
标签:CF718A 题解 s1 ++ st break int Strange 进位

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

相关文章

  • P10511 方差 题解
    【题目简述】定义一个长度为\(n\)的序列\(a\)的方差为:\(s^2=\frac{1}{n}\sum_{i=1}^n(a_i-\overline{a})^2\)。\(\sum\)为累加求和符号,\(\overline{a}\)为序列\(a\)的平均数。给定\(m\)个形如\([l,r,b]\)的组合,表示\(a_l,a_{l+1},\ldots,a_r\)为\(b\)。给定......
  • 洛谷P2696之慈善的约瑟夫——题解
    洛谷P2696题解[传送锚点](P2696慈善的约瑟夫-洛谷|计算机科学教育新生态(luogu.com.cn))比不过大佬,从蒟蒻做起选择比较水有意思的解法——用队列模拟(还是窝太弱了)正片开始考虑队列模拟,因为每次都是假的剔除,所以我们的目标是找到每回游戏的最终存活者。将不被剔除,......
  • 题解:Pinely Round 4 (Div. 1 + Div. 2) C
    C.AbsoluteZerotimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)of\(n\)integers.Inoneoperation,youwillperformthefollowingtwo-stepmove:Choose......
  • Codeforces 11D A Simple Task 题解 [ 蓝 ] [ 状压 dp ]
    思路不难想,细节比较多。思路观察到\(n\le19\),首先想到状压dp。于是自然地定义\(dp[j][i]\)为:抵达点的状态为\(i\),且此时在点\(j\)时,简单路径的条数。注意这里是简单路径的条数,而不是环的个数,因为环的个数要在dp过程中统计。这里的dp作用就在于求简单路径条数。......
  • [JOI 2020 Final] 火事 题解
    给一篇题解。(下面这张图是从luogu上粘贴的,因为不太会画图)其中纵坐标为\(t\),横坐标为\(a_i\)。发现同颜色块只有平行四边形和直角梯形(等腰直角三角形)两种情况。可以将直角梯形削去左下角,分成两部分考虑。等直可以直接暴力插入区间,总个数\(O(n)\)。平行四边形可以看作上......
  • [CF455D] Serega and Fun 题解
    不知道大家做没做过数列分块基础9题?插入删除操作可以用链表,线段树等数据结构都不好维护,考虑分块。对于修改操作,暴力重构受影响块的链表,发现除首尾块外,其他块都可以看作是区间左移一位,所以加头删尾即可。每个块开一个数组(绝对不能是\((un\_)map\),不然你会和我一样死的很诡异),表示......
  • HDU2024 R2 T9 题解
    考虑维护一下每个点的速度。把区间加拆成后缀加和后缀减,然后考虑后缀加。减就同理。考虑在一段后缀的目标速度增加之后,哪些时刻的加速度会变化。这里加速度必然只会变大\(1\),因此在这个时刻之后的速度都会增加\(1\),又由于目标速度也增加了\(1\),所以这个位置之后的加速度都不再......
  • CF455D Serega and Fun 题解
    Beforeit来当一回教练的题解翻译家,平衡树这种高级算法自然是不会的,所以详细讲一下STL。成为蒟蒻(也就是自己)的福音。Solution我们观察到题目要求“把第\(r\)个数插入在第\(l\)个数之前,其他数顺序不变“,使用\(deque\)的\(push\)_\(front\)和\(push\)_$back$操作可......
  • 暗区突围pc端下载失败/卡正在初始化/连接伺服务器失败/问题解决方法
    暗区突围pc端下载失败/卡正在初始化/连接伺服务器失败/问题解决方法暗区突围pc端下载失败/卡正在初始化/连接伺服务器失败/问题解决方法暗区突围也可以在电脑上游玩拉,暗区突围PC端上线在即,本次上线就是全球抢先测试了,很多小伙伴在游戏下载过程中遇到了很多问题,比如:下载失......
  • QOJ6504 Flower‘s Land 2 题解
    QOJ6504Flower'sLand2题解题目链接:QOJ6504Flower'sLand2题意:给定一个只包含\(0,1,2\)的序列,\(T\)次询问,询问有两种:区间所有数加\(1\)然后模\(3\)求一段区间能否通过每次删掉相邻两个相同的数删完(如\(1,0,0,2,2,1\)就满足条件)题解:考虑用什么方法来维护区间......