Problem #3290 - ECNU Online Judge

7 年，3 月前

本渣做这题的心路历程如下：
先标记第一个升序出现的点比如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))

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

回复 4 0

10132130138

7 年，3 月前

老哥稳

回复 0 0

10175102262 LarsPendragon

6 年，9 月前

附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;
}

回复 2 0

Fifnmar

4 年，11 月前

这道题的想法：

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();
    }
}

回复 0 0

EdmundYan

4 年，11 月前

倒序遍历

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))

回复 0 0

3290. 找数(II)

服务

开源

关于我们