卡片游戏
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1088 Accepted Submission(s): 341
Problem Description
小明最近宅在家里无聊，于是他发明了一种有趣的游戏，游戏道具是N张叠在一起的卡片，每张卡片上都有一个数字，数字的范围是0~9，游戏规则如下：
首先取最上方的卡片放到桌子上，然后每次取最上方的卡片，放到桌子上已有卡片序列的最右边或者最左边。当N张卡片全部都放到桌子上后，桌子上的N张卡片构成了一个数。这个数不能有前导0，也就是说最左边的卡片上的数字不能是0。游戏的目标是使这个数最小。
现在你的任务是帮小明写段程序，求出这个最小数。
Input
第一行是一个数T，表示有T组测试数据；
然后下面有T行， 每行是一个只含有0~9的字符串，表示N张叠在一起的卡片，最左边的数字表示最上方的卡片。
[Technical Specification]
T<=1000
1 <= N <= 100
Output
对于每组测试数据，请在一行内输出能得到的最小数。
Sample Input
3
565
9876543210
9876105432
Sample Output
556
1234567890
1678905432
思路:
一开始太轻敌了,速度敲,速度wa,哎! 惭愧,首先思路是贪心,有一点我们肯定能想到,最高位的数字越小那么这个数就越小,首先我们考虑第一位,我们找到最小的并且最靠后的,然后最小的那个肯定是第一位,最小的后面的那些肯定是最靠后的,并且顺序不能改变,找到最小的可以理解,那为什么是最靠后的呢? 因为想下,靠后就说明他是后拿出来的,后拿出来的又是最小的肯定是最前面的那位,而如果他是最前面那位以后前面就不能在加数了,所以后面的就直接是最后面的,就这样,第一次我们找到了答案的第一个数字和最后面的一组数据,
注意一点第一个不能为0,第二步就找的是前面第二个数据和最后倒数第二组数据,第三步........找到最后就行了...
#include<stdio.h> #include<string.h> #define N 500 #define INF 1000000000 int num[N]; int ans[N]; char str[N]; int main () { int t ,l ,r ,n ,tt ,i; scanf("%d" ,&t); while(t--) { scanf("%s" ,str); n = strlen(str); for(i = 1 ;i <= n ;i ++) num[i] = str[i- 1] - 48; l = 0 ,r = n + 1; tt = n; while(tt) { int min_num = INF; int min_id = -1; for(i = tt ;i >= 1 ;i --) { if(min_num > num[i]) { if(tt == n && !num[i]) continue; min_num = num[i]; min_id = i; } } ans[++l] = min_num; for(i = tt ;i > min_id ;i --) ans[--r] = num[i]; tt = min_id - 1; } for(i = 1 ;i <= n ;i ++) printf("%d" ,ans[i]); puts(""); } return 0; }