题解：P13159 [GCJ 2017 Qualification] Tidy Numbers

· · 题解

P13159 Tidy Numbers - Solution

Problem Statement

给定一个数 N，你要将它改为小于等于原数，且各位数字不递减的最大数。

Analysis

首先分情况讨论，若原数满足条件，则不必修改。否则，分析满足性质的数字。

设初次不符合规则的位置为 x，即 N_x>N_{x+1}，先将 N_x\gets N_x-1，也就是相当于退一位，这样才能满足小于原数。

再考虑后面的位数，由于已经满足 N_x-1<N_x，因此后面的数字不会决定两数的大小关系，全部设为 9 一定是最优的。

这样，就粗略地证明了贪心的正确性，可以实现。

Approach

使用字符串存储 N，字符串为 S。遍历找到 x，S_x\gets S_x-1，再将后面的 S_i\gets9，其中 i\in(x,n]。由于每次更新后可能仍然不合条件，所以要循环此操作，直到全串符合为止。

最后还要注意去掉前导零，使用 while(s[i]=='0') i++ 就可以实现。

Code

#include<bits/stdc++.h>
using namespace std;
string s;

void solve(){
    for(int i=1;i<s.size();i++){
        if(s[i-1]>s[i]){ //找x 
            s[i-1]--;
            for(int j=i;j<s.size();j++)
                s[j]='9';
            solve();
        }
    }
}

void print(){
    int i=0;
    while(s[i]=='0') //去除前导零 
        i++;
    for(i;i<s.size();i++)
        cout<<s[i];
    cout<<endl;
}

int main(){
    int T;
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>s;
        solve(); 
        printf("Case #%d: ",t);
        print(); //输出答案，处理前导零 
    } 
    return 0;
}