Microsoft在线编程测试热身题(hiho密码)

hiho密码

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
小Ho根据最近在密码学课上学习到的知识，开发出了一款hiho密码，这款密码的秘钥是这样生成的：对于一种有N个字母的语言，选择一个长度为M的单词；将组成这个单词的所有字母按照顺序不重复的写出（即遇到相同字母时跳过）；然后将字母表剩下的没有使用过的字母按照顺序在其后进行排列。
如对于有5个字母的hiho语，选择单词1, 2, 2, 4, 3（此处数字表示字母在字母表中的顺序），则秘钥为1,2,4,3,5。
但是有一天小Ho在计算出了秘钥之后，却发现他弄丢了一开始选择的单词，于是他找到了你，希望你能够帮他找到能够生成这个秘钥的最短的单词。
输入
每个输入文件包含单组测试数据。
每组测试数据的第一行为一个正整数N，意义如前文所述。
每组测试数据的第二行为N个正整数，用来描述一个秘钥，其中第i个正整数Ai表示秘钥的第i个字符在字母表中的顺序。
对于100%的数据，满足N<=1000，1<=Ai<=N。
对于100%的数据，满足对于任意1<=i, j<=N，若i≠j，则Ai≠Aj。
输出
对于每组测试数据，输出能够生成输入给出的秘钥的最短的单词（空串不认为是单词）。由于字母表没有给出，所以对于每个字母，输出其在字母表中的顺序即可（用空格隔开）。
样例输入
5
1 2 4 3 5
样例输出
1 2 4

解题思路：

这道题题干很长，对于题目的理解可能需要一定的时间。但是一旦静下心来理解透了的话，还是很容易做的。不过这毕竟只是微软用来让在线编程测试的人热身的一道题，真正的考试题还是会有一定难度的，会选拔出来真正优秀的程序员的，有志于此的朋友们还是要打好基础，不可掉以轻心。
在看懂这道题之后，算法还是很容易想出来的，只要想通以下几点：

1. 最短的单词肯定是不会有重复字母的。
2. 原单词里可以出现逆序，但是字母表剩下的未使用过的字母一定是顺序排列的，且字母表剩下的字母排列在密钥的后面。
3. 原单词至少也有一个字母，不会为空。

想通了以上三点，我们就很容易得到算法了，我的做法是，密钥从后往前遍历，直到发现了逆序对才停止，从停止的位置到密钥的起始端都必须是原单词里的字母了。然后最后输出的时候注意一下(1.原单词不能为空 2.N==1的情况)就好了。
C++代码如下：

#include <iostream>
using namespace std;

int main(){
    int N;
    int array[1010];
    cin >> N;
    for (int i=0; i<N; ++i)
        cin >> array[i];
        
    int j;
    if (N == 1)
        cout << array[0];
    else{
        for (j=N-2; j>=0; --j)
            if (array[j] > array[j+1])
                break;
        if (j == -1)
            cout << array[0];
        else{
            for (int i=0; i<=j; ++i)
                cout << array[i] << ' ';
        }
    }
    return 0;
}

最后，关于时间复杂度的问题，这道题也很容易看出来时间复杂度为O(N)。