题解 CF95B 【Lucky Numbers】

· · 题解

题意求大于等于n的最小幸运数，（幸运数是只由4和7构成，且4和7的数量相等的数）。

首先可以知道幸运数的位数一定是偶数位的，如果n是奇数位的，直接输出(n+1)/2个4和(n+1)/2个7。

接下来，从n的最高位开始遍历：1. 如果n的这位数字（记为a[i])小于等于4, 4的个数（记为c4）就加1。

（1）如果c4已经超过了n的总位数的一半（记为h），把幸运数的这位数(记为b[i])设成7，停止遍历。

（2） 否则当a[i]小于4，停止遍历。当a[i]等于4，记录位置(记为p4[c4])以及当前b[i]等于7有多少个（记为c[c4])，继续遍历。

2.如果a[i]小于等于7，7的个数（记为c7）就加1。

（1）如果c7已经超过了h，找离它最近且c[c4]小于h的4的位置，把4改成7，停止遍历。 如果没有这样的4的位置，做个标记，位数和n相等的幸运数不存在。

（2）否则当a[i]小于7，停止遍历。当a[i]等于7，继续遍历。

3.如果a[i]大于7，找离它最近且c[c4]小于h的4的位置，把4改成7，停止遍历。 如果没有这样的4的位置，做个标记，位数和n相等的幸运数不存在。

最后，输出符合要求结果即可。 程序的复杂度是线性的，代码如下：

#include <stdio.h>
#include <string.h>
#define N 100005

char a[N], b[N];
int p4[N], c[N];

int main() 
{
    int i, j, c4 = 0, l, h, c7 = 0, f = 0;

    scanf("%s", a);
    l = strlen(a);
    if(l & 1){
        h = (l + 1) >> 1;
        for(i = 0; i < h; i++) putchar(52);
        for(i = 0; i < h; i++) putchar(55);
        return 0;
    }
    else{
        h = l >> 1;
        for(i = 0; i < l; i++){
            if(a[i] <= 52){
                c4++;
                if(c4 > h){
                    b[i] = 55;
                    c4--, c7++;
                    break;
                }
                else{
                    b[i] = 52;
                    if(a[i] < 52) break;
                    p4[c4] = i;
                    c[c4] = c7;
                }
            }
            else if(a[i] <= 55){
                c7++;
                if(c7 > h){
                    while(c4 > 0 && c[c4] >= h) c4--;
                    if(c4 == 0){
                        f = 1;
                        break;  
                    }
                    b[i = p4[c4]] = 55;
                    c7 = c[c4] + 1;
                    c4--;
                    break;
                }
                else{
                    b[i] = 55;
                    if(a[i] < 55) break;
                }
            }
            else{
                while(c4 > 0 && c[c4] >= h) c4--;
                if(c4 == 0){
                    f = 1;
                    break;  
                }
                b[i = p4[c4]] = 55;
                c7 = c[c4] + 1;
                c4--;
                break;
            }
        }
    }
    if(f){
        i = h + 1;
        while(i--) putchar(52);
        i = h + 1;
        while(i--) putchar(55);
    }
    else{
        if(i == l) i--;
        for(j = 0; j <= i; j++) putchar(b[j]);
        i = h - c4;
        while(i--) putchar(52);
        i = h - c7;
        while(i--) putchar(55);
    }

    return 0;
}