首页 > ACM题库 > HDU-杭电 > HDU 4550-卡片游戏-贪心-[解题报告]HOJ
2015
07-25

HDU 4550-卡片游戏-贪心-[解题报告]HOJ

卡片游戏

问题描述 :

  小明最近宅在家里无聊,于是他发明了一种有趣的游戏,游戏道具是N张叠在一起的卡片,每张卡片上都有一个数字,数字的范围是0~9,游戏规则如下:
  首先取最上方的卡片放到桌子上,然后每次取最上方的卡片,放到桌子上已有卡片序列的最右边或者最左边。当N张卡片全部都放到桌子上后,桌子上的N张卡片构成了一个数。这个数不能有前导0,也就是说最左边的卡片上的数字不能是0。游戏的目标是使这个数最小。
  现在你的任务是帮小明写段程序,求出这个最小数。

输入:

第一行是一个数T,表示有T组测试数据;
然后下面有T行, 每行是一个只含有0~9的字符串,表示N张叠在一起的卡片,最左边的数字表示最上方的卡片。

[Technical Specification]
T<=1000
1 <= N <= 100

输出:

第一行是一个数T,表示有T组测试数据;
然后下面有T行, 每行是一个只含有0~9的字符串,表示N张叠在一起的卡片,最左边的数字表示最上方的卡片。

[Technical Specification]
T<=1000
1 <= N <= 100

样例输入:

3
565
9876543210
9876105432

样例输出:

556
1234567890
1678905432

/*
分析:
    贪心贪的我好恶心。。。
    毫无疑问的,越是位数高的数字、其数值越小越好。
    先找到非0的、最小的、在字符串中最靠后的数字,这个数
就是ans的第一位了,串中的这个数字后面的数字一定为ans后面
部分;
    重复上述步骤,不过这次开始找到的最小值可以是0。

                                             2013-06-06
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=105;

int l,r;
char str[N],ans[N];
void find(int a,int b)
{
	if(b<a)	return ;
	int i,index;
	char min;
	min='9'+1;
	for(i=b;i>=a;i--)	if(str[i]<min)	{min=str[i];index=i;}
	for(i=b;i>index;i--)	ans[r--]=str[i];
	ans[l++]=str[index];
	find(a,index-1);
}
int main()
{
	int T;
	int i;
	int index,len;
	char min;
	cin>>T;
	while(T--)
	{
		scanf("%s",str);
		len=strlen(str);
		min='9'+1;
		for(i=len-1;i>=0;i--)
		{
			if(str[i]=='0')	continue;
			if(str[i]<min)	{min=str[i];index=i;}
		}
		if(min=='9'+1)
		{
			while(len--)	printf("0");
			cout<<endl;
			continue;
		}
		l=0;r=len-1;
		ans[l++]=min;
		for(i=len-1;i>index;i--)	ans[r--]=str[i];
		
		find(0,index-1);
		for(i=0;i<len;i++)	printf("%c",ans[i]);
		cout<<endl;
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/9040693