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

CPP

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

题解：P13159 [GCJ 2017 Qualification] Tidy Numbers

文章操作