题解：P13435 [GCJ 2009 #1B] The Next Number

· · 题解

P13435适合大多数选手的方法。

思路：

本题是求下一个排列的升级版。将每组输入的数以字符串的形式读入，方便提取每一位上对应的数字。谈及新数的构成方式，这里我们分类讨论：

  1. 首先考虑“刚刚写下的最后一个数”每一位上的数均非递增的情况。将其中最小的非零数作为最高位，次高位为零，其余数位用剩下的数字从小到大依次分配即可。

  2. 一般情况下的处理方式与前者相比较为复杂。循环从后往前找到第一组（i，i+1）满足 a[i]<a[i+1]，先原封不动输出 a[1] 至 a[i-1]，借助优先队列确定 a[i] 到 a[n] 中大于 a[i] 的最小的数 x 并输出。其余的从小到大依次输出。

AC CODE：

#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int main(){
    //快读可根据需求自行添加（本题时限为2、3秒）。
    cin>>t;
    for(int tt=1;tt<=t;tt++){
        cin>>s;
        int pre=0,flag=-1,x;//pre记录上一位数，falg判断是否非递增。
        priority_queue<int,vector<int>,greater<int> >q,q1;//优先队列。
        for(int i=s.size()-1;i>=0;i--){
            if((s[i]-'0')>=pre){//大于或等于上一个数，入队。
                q.push(s[i]-'0');
                pre=s[i]-'0';//更新上一个。
            }else{
                flag=i;//第2中情况。
                while(!q.empty()){//找第一个大于s[i]-'0'的数。
                    if(q.top()<=(s[i]-'0')){
                        q1.push(q.top());//q1为辅助数组。
                        q.pop();
                    }else{
                        x=q.top();
                        q.pop();
                        break;
                    }
                }while(!q1.empty()){
                    q.push(q1.top());
                    q1.pop();
                }
                q.push(s[i]-'0');
                break;
            }
        }
        cout<<"Case #"<<tt<<": ";//标准格式。
        if(flag!=-1){//情况一。
            if(flag)cout<<s.substr(0,flag)<<x;
            else cout<<x;
            while(!q.empty()){
                cout<<q.top();
                q.pop();
            }
        }else{//情况二。
            int ans=1;
            while(!q.empty()){
                if(q.top()==0){
                    ans++;
                    q.pop();
                }else{
                    cout<<q.top();
                    q.pop();
                    break;
                }
            }while(ans--){
                cout<<"0";
            }while(!q.empty()){
                cout<<q.top();
                q.pop();
            }
        }
        cout<<"\n";
    }
    return 0;//好习惯。
}