从零开始的算法题生活 (一)

引言

深切感受到智商的重要性，所以随后会不定期练习算法题，大约最晚间隔不会超过一周，每次一道，就当大脑训练，以上。刷的网站也随机看心情，目前决定用 hihoCoder,以下为这次刷的题。

hiho 密码

描述

小 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

分析解答

这道题编程到不困难，难点在于整道题的分析理解上，只要理解了，很容易就写出来了。重点就在于观察单词后面的字母是绝对不可能有逆序的，所以从后往前遍历，第一个逆序点就是最短的单词的末尾。有了思路，程序如下(gcc 6,3,1):

#include<stdio.h>
int main(void){
        int n;
        int i;
        int flag=0;
        scanf("%d",&n);
        int array[n];
        for(i=0;i<n;i++)
        {
                scanf("%d",&array[i]);
        }
        for(i=n-1;i>0;i--){
                if(array[i-1]>array[i]){
                        flag=i-1;
                        break;
                }

        }
        for(i=0;i<=flag;i++)
                printf("%d ",array[i]);
        return 0;
}
~    
ps:此处要考虑下临界值，比如n为1的情况，我一开始就由于没有考虑到1导致部分测试用例无法通过