ACM模版

描述

题解

做这个题需要敏锐的观察力……像我这样反应迟钝的人只能多 T 几发才知道。

当读第一遍题时，我就很奇怪， 1≤n≤105 ，而 0≤k≤109 ， k 这么大肯定会超时，但是当我看到描述中如果没有相应的 x 时就结束，所以大意了，以为当 k 很大时肯定会直接跳出来……谁成想，扫描一遍 T 了，各种优化了几发还是 T 。

再仔细想想，发现，或许里面存在来回倒腾的情况呢？那样的话岂不是肯定会 T 了？这样的话，从 n、k 的数据范围来看，早就该想到这个问题了。

经过模拟发现：

4 4 7≫4 7 7≫4 4 7≫4 7 7……(key:1 2 3)

所以遇见这个情况时直接判断需要倒腾多少趟即可。

代码

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 10;

int n, k;
char d[MAXN];

int main(int argc, const char * argv[])
{
    scanf("%d%d%s", &n, &k, d + 1);

    for (int i = 1; i < n && k; i++)
    {
        if (d[i] == '4' && d[i + 1] == '7')
        {
            k--;
            if (i & 1)
            {
                d[i + 1] = '4';
                if (d[i + 2] == '7')
                {
                    if (k & 1)
                    {
                        d[i + 1] = '7';
                    }
                    break;
                }
            }
            else
            {
                d[i] = '7';
                if (d[i - 1] == '4')
                {
                    if (k & 1)
                    {
                        d[i] = '4';
                    }
                    break;
                }
            }
        }
    }

    puts(d + 1);

    return 0;
}