首页 > ACM题库 > HDU-杭电 > HDU 3283-The Next Permutation-字典树-[解题报告]HOJ
2014
03-13

HDU 3283-The Next Permutation-字典树-[解题报告]HOJ

The Next Permutation

问题描述 :

For this problem, you will write a program that takes a (possibly long) string of decimal digits, and outputs the permutation of those decimal digits that has the next larger value (as a decimal number)
than the input number. For example:
123 -> 132
279134399742 -> 279134423799
It is possible that no permutation of the input digits has a larger value. For example, 987.

输入:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by up to 80 decimal digits which is the input value.

输出:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by up to 80 decimal digits which is the input value.

样例输入:

3
1 123
2 279134399742
3 987

样例输出:

1 132
2 279134423799
3 BIGGEST

STL中的一个函数next_permutation()的运用~~

这道题就是传说的字典树~~

不太懂~~在网上找到这个题解~~

必须理解这个函数是怎么写的~~~

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include <cstring>
using namespace std;
char a[100];
int main()
{
    int t,i,len,n;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d %s",&n,a);
        len=strlen(a);
        if (next_permutation(a,a+len)) printf("%d %s\n",i,a);
        else
          printf("%d BIGGEST\n",i);
    }
    return 0;
}

参考:http://blog.csdn.net/xxx_bug/article/details/7215174