RIMSKI 题解_C_内存溢出

1.罗马数字简介

**
罗马数字是阿拉伯数字传入之前使用的一种数码。其采用七个罗马字母作数字、即Ⅰ（1）、X（10）、C（100）、M（1000）、V（5）、L（50）、D（500）。记数的方法：

相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；
小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；
小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9；
在一个数的上面画一条横线，表示这个数增值 1,000 倍，如
=5000。

它的产生晚于中国甲骨文中的数码，更晚于埃及人的十进位数字。但是，它的产生标志着一种古代文明的进步。
我国 20 世纪 60～70 年代发行的第三套人民币冠字号码中也采用了罗马数字。此外，在书稿章节及科学分类时也有采用罗马数字的。
21 世纪，罗马数字已是一种应用较少的一种的数量表示方式。罗马数字主要用于某些代码，如产品型号等。有的钟表表面仍有用它表示时数的。计算机 Unicode码收录有合体的罗马数字 1～12和50、100、500、1000。由于书写繁难，所以后人很少采用。
**

2.罗马数字如何表示

如果一个n位数用罗马数字表示，可以看作n个位数进行拼接。比如给定一个3位数578，可以拆成百位数5，十位数7，个位数8。那么我们就可以得到578=500+70+8。把其换成罗马数字可得"D"+“LXX”+“VIII”=DLXXVIII,因此578用罗马数字可以表示为DLXXVIII。再比如一个二位数95，可以拆成十位数9和个位数5，95=90+5。换成罗马数字可得"XC"+“V”=XCV,其它的罗马数字表示也是同理。

3.RIMSKI

题目背景

本题为COCI 2009-2010 2nd round T2 RIMSKI

分值按原题设置，满分 50。
题目描述

给定一个罗马数字 B，把 B 的字符重新排列，要求让排列后的数字最小。
输入格式

一行一个罗马数字 B。
输出格式

一行一个罗马数字，为你重排后能得到的最小的数字。
输入输出样例
输入 #1

VIII

输出 #1

VIII

输入 #2

输出 #2

输入 #3

III

输出 #3

III

输入 #4

输出 #4

说明/提示

1≤B<100。

注意，在本题中I如果在大数字之前，它只能在V 、X之前。输入遵循同样的规则。（这就是样例 4 的输出为什么是 LI 而不是 IL。）

算法设计

**
方法一
在了解罗马数字的基础上，先把个位数部分，十位数部分所有的可能枚举出来，再通过排列组合的方式得到1-99的所有组合，从1枚举到99，最先枚举的元素组成的个数与输入的罗马数字的元素组成的个数相等时，即为最小的数字。

#include 
using namespace std;
string s1[10]={"","I","II","III","IV","V","VI","VII","VIII","IX"};
string s2[10]={"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
string s;
int cnt[5]={0};
int main()
{
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		switch(s[i])
		{
			case 'I':
				cnt[0]++;
				break;
			
			case 'V':
				cnt[1]++;
				break;
			
			case 'X':
				cnt[2]++;
				break;
			
			case 'L':
				cnt[3]++;
				break;
				
			case 'C':
				cnt[4]++;
				break;
		}
	}
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<10;j++)
		{
			int cnt2[5]={0};
			for(int k=0;k<s1[j].length();k++)
			{
				switch(s1[j][k])
				{
					case 'I':
						cnt2[0]++;
						break;
					
					case 'V':
						cnt2[1]++;
						break;
					
					case 'X':
						cnt2[2]++;
						break;
				}
			}
			
			for(int k=0;k<s2[i].length();k++)
			{
				switch(s2[i][k])
				{
					case 'X':
						cnt2[2]++;
						break;
					
					case 'L':
						cnt2[3]++;
						break;
						
					case 'C':
						cnt2[4]++;
						break;
				}
			}
			
			if(cnt[0]==cnt2[0]&&cnt[1]==cnt2[1]&&cnt[2]==cnt2[2]&&cnt[3]==cnt2[3]&&cnt[4]==cnt2[4])
			{
				cout<<s2[i]<<s1[j]<<endl;
				return 0;
			}
		}
	}
}

方法二

因为题目给定的范围在1~99，所以有如下更简单的方法：
这个方法不太好讲，也不推荐，代码如下，请慢慢意会吧…

#include 
using namespace std;
char s[110];
int main()
{
	scanf("%s",s);
	int len=strlen(s);
	if(s[0]=='L'&&s[1]=='X'&&s[2]=='I')
	{
		cout<<"XLI";
		return 0;
	}
	if(s[len-1]=='I'&&(s[len-2]=='X'||s[len-2]=='V'))
		swap(s[len-2],s[len-1]);
	if(s[0]=='L'&&s[1]=='X'&&s[2]!='X')
		swap(s[0],s[1]);
	for(int i=0;i<len;i++)
	{
		cout<<s[i];
	}
	return 0;
}