3290. 找数(II)

╮ 潜心 ╰

本渣做这题的心路历程如下:
先标记第一个升序出现的点 比如34522 升序在第一个位置出现 就用一个变量i存了0这个位置
然后就开始遍历字符串 找位置 但是发现54323和54321的i都是4 所以就想用一个变量flag存一下 表示原字符串是否已经是非上升数
好 假设这些都做完了 该存都存了 然后把i前的字符照样输出 i处+1 i后全为0
比如 534533 输出就是540000

提交后结果WA了 开始反思找反例
就想到4223这个反例 一次上述操作后变成4230 但是这样得到的结果依旧不是非上升数
于是诞生了一个新思路:重复该操作直到符合为止
提交 AC 现附上代码

cas = int(input())
for t in range(cas):
        s = input()
        flag = 0
        if len(s) != 1:
                while flag == 0:
                        for i in range((len(s) - 1)):
                                if int(s[i]) < int(s[i+1]):
                                        flag = 0
                                        s = s[:i] + str(int(s[i])+1) + "0"*(len(s) - i - 1)
                                        break
                                if i == len(s) - 2:
                                        flag = 1
                                        break
        print("case #%d:\n%s" %(t, s))

改错尽管有时很累 =。= 但是只要洞悉到题目本质 往往很容易能找到解决方案

10132130138

老哥稳

10175102262 LarsPendragon

附C代码,感谢潜心大佬的提示。

#include <stdio.h>
#include <string.h>
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        char num[20];
        int l, i;
        scanf("%s",num);
        l=strlen(num);
        for(i=0; i<l-1; i++)
        {
            if(num[i]<num[i+1])
            {
                for(; num[i]==num[i-1]; i--);
                num[i]++;
                for(++i; i<l; i++)
                    num[i]='0';
                break;
            }
        }
        printf("case #%d:\n",I);
        for(i=0; i<l; i++) printf("%c",num[i]);
        printf("\n");
    }
    return 0;
}
EdmundYan

倒序遍历

times=int(input())
for time in range(times):
        num=input()
        if len(num)>1:
                for i in range(len(num)-2, -1, -1):
                        curval=int(num[i])
                        if curval<int(num[i+1]):
                                curval+=1
                                num=num[:i]+str(curval)+"0"*(len(num)-1-i)
print("case #%d:\n%s" %(time,num))
Deuchie

这道题的想法:

1.首先,我是用字符串来储存这个数的(用long long也行但是比较麻烦,因为这道题要研究每一个数位)。
2.第一步是遍历这个数(字符串),找到出现了上升的位置(前一个比后一个小的位置)。
3.根据分析可以得知,只有让它前面的那个数位+1,此后的所有数位全为0,才能满足题意。
4.但现在出现了一个新的问题:将前面的数位+1后,是否会造成前面本来的非上升状态被打破呢?所以我从第一步记录下来的点开始向前遍历,重复前一步的操作,直到前面的数位不再小于后面的数位,或者遍历到了首位。对于到了首位的情况,应该特判一下进位。
5.最后,上面的朴素想法可以优化:把后面数位置0的操作可以放到最后一起,不用重复置0。

最终代码:

#include <iostream>
#include <string>
using namespace std;

void solve() {
    string a;
    cin >> a;
    int sz = a.size();
    int i;
    for (i = 1; i < sz; ++i)
        if (a[i - 1] < a[i])
            break;
    if (i != sz) {
        while (i > 0 && a[i - 1] < a[i])
            ++a[--i];
        for (int j = i + 1; j < sz; ++j)
            a[j] = '0';
        if (a[0] > '9') {
            cout << '1';
            a[0] -= 10;
        }
    }
    cout << a << '\n';
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cout << "case #" << i << ":\n";
        solve();
    }
}
你当前正在回复 博客/题目
存在问题!