OD机试题

OD机考原题

1.恢复数字序列

对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字.

输入描述
输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符审长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。

输出描述
输出一个数字，为序列中最小的数字

示例1：
输入
19801211 5
输出
8
说明：正常的数字序列为8 9 10 11 12 这5个数字，最小数字为8 作者：天生完美

int main(){
	string strInput;//输入数字序列
	int n;//输入n个连续的整数
	cin>>strInput>>n;
	
	bool bok=false;
	for (int i=1;i<1000;i++)
	{
		string tmp = strInput;
		for (int j=0;j<n;j++)
		{
			int num = i+j;
			char cc[2];
			bool bfind=true;
			//借用while循环判断第j个整数的每一位，是否都能在序列中找到，如果能找到，则在原序列中删除该整数的所有数字
			while (num != 0)
			{
				itoa(num%10,cc,10);
				int pos = tmp.find(cc);
				if (pos == string::npos)
				{
					 bfind=false;
					break;
				}
				tmp.erase(pos, 1);
				num = num/10;				
			}
			
			if (!bfind)
			{
			    //没有找到第j个整数，跳出循环
				break;
			}
	
			//找到连续相加的所有整数的条件，原序列等于空且j为最后一个整数
			if (j==n-1 && tmp == "")
			{
				bok = true;
			}
		}
		if (bok)
		{
			cout<<i<<endl;
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

2.比赛

一个有N个选手参加比赛，选手编号为1~N（3<=N<=100），有M（3<=M<=10）个评委对选手进行打分。
打分规则为每个评委对选手打分，最高分10分，最低分1分。
请计算得分最多的3位选手的编号。
如果得分相同，则得分高分值最多的选手排名靠前
(10分数量相同，则比较9分的数量，以此类推，用例中不会出现多个选手得分完全相同的情况)。

输入描述：
第一行为半角逗号分割的两个正整数，第一个数字表示M（3<=m<=10）个评委，第二个数字表示N（3<=N<=100）个选手。
第2到M+1行是半角逗号分割的整数序列，表示评委为每个选手的打分，0号下标数字表示1号选手分数，1号下标数字表示2号选手分数，一次类推。

输出描述：
选手前三名的编号。
注：若输入为异常，输出-1，如M、N打分不在范围内，或残才选手和评委数不在范围内。

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4,5
10,6,9,7,6
9,10,6,7,5
8,10,6,5,10
9,10,8,4,9

输出
2,1,5
说明：第一行代表有4个评委，5个选手参加比赛

矩阵代表是4*5，每个数字是选手的编号，每一行代表一个评委对选手的打分排序，

2号选手得分36分排第1，1号选手36分排第2，5号选手30分(2号10分值有3个，1号10分值只有1个，所以2号排第一)

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例

输入
2,5
7,3,5,4,2
8,5,4,4,3

输出
-1
说明
只有2个评委，要求最少为3个评委

示例3 输入输出示例仅供调试，后台判题数据一般不包含示例

输入
4,2
8,5
5,6
10,4
8,9

输出
-1
说明
只有2名选手参加，要求最少为3名

示例4 输入输出示例仅供调试，后台判题数据一般不包含示例

输入
4,5
11,6,9,7,8
9,10,6,7,8
8,10,6,9,7
9,10,8,6,7

输出
-1
说明
第一个评委给第一个选手打分11，无效分数

struct core{
	int id;//选手编号
	int cores;//选手的总分数
	int num[11];//分数1-10的个数
}; 

bool cmp(core c1, core c2){
	if (c1.cores != c2.cores)
	{
		return c1.cores > c2.cores;//降序
	}
	//分数相同时，比较最大分数的个数，降序排序
	for (int i=10;i>0;i--)
	{
		if (c1.num[i] != c2.num[i])
		{
			return c1.num[i] > c2.num[i];
		}
	}
}
int main(){
	// 获取选手 n 和评委 m 的个数
	cout<<"输入选手和评委个数"<<endl;
	int m;
	int n;
	cin>>m;
	cin.get();
	cin>>n;
	if (n<3 || n>100 || m<3 || m>10)
	{
		cout<<-1;
		return;//选手或评委的人数不在范围内
	}
	//填充数组
	vector<vector<int>> vecData(m,vector<int>(n,0));
	for (int i=0;i<m;i++)
	{
		vector<int> tt(n,0);
		for (int j=0;j<n;j++)
		{
			int tmp ;
			cin>> tmp;
			if (tmp>10 || tmp<1)
			{
				cout<<-1;//分数不在范围内
				return;
			}
			tt[j] = tmp;
			if (cin.get()=='\n')
			{
				vecData[i] = tt;
				break;
			}
		}
	}

	vector<core> vecCor ; 
	//统计选手总分数以及1-10的个数
	for (int i=0;i<n;i++)
	{
		core cc;
		memset(&cc,0,sizeof(core));
		cc.id = i+1;
		cc.cores = 0;
		
		for (int j=0;j<m;j++)
		{
			int tmp = vecData[j][i];//评委打的分数
			cc.cores+=tmp;
			cc.num[tmp]++;
		}
		vecCor.push_back(cc);		
	}
	//自定义排序规则
	sort(vecCor.begin(),vecCor.end(),cmp);

	//输出前三的id
	//cout<<"前三名选手的id是：";
	for (int i=0;i<3;i++)
	{
		cout<<vecCor[i].id<<" ";
	}
	cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84