[数据结构与算法]CSP-201609-2-火车购票 - 90分原因分析及满分参考

一、90分代码

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int p,i,j,k,sum;
	int a[100];
	for(i=0;i<=100;i++)
	{
		a[i]=0;//空位置
	}
	for(i=0;i<n;i++)
	{
		cin>>p;
		for(j=1;j<=100;j++)
		{
			if(p==sum)//j=11
			{
				k=j-p;//k=6
				int d;
				for(d=k;d<j;d++)//6 7 8 9 10
				{
					if(a[d]==0)
					{
						a[d]=1;
						cout<<d<<" ";
					}
				}
				cout<<endl;
				sum = 0;
				break;
			}
			if((j-1)%5==0)
			{
				sum=0;
			}
			if(a[j]==0)
			{
				sum++;
			}
		}
	}
}

二、原因分析

• 没考虑，“没有连坐的位置，要选最小的几个空位”的情况
• 且数组只开了a[100]，溢出了呀… …

三、满分代码

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int p,i,j,k,sum;
	int a[101];
	for(i=0;i<=100;i++)
	{
		a[i]=0;//空位置
	}
	for(i=0;i<n;i++)
	{
		cin>>p;
		sum = 0;
		for(j=1;j<=100;j++)
		{
			
			if(j%5==1)
			{
				sum=0;
			}
			if(a[j]==0)
			{
				sum++;
			}
			if(p==sum)//j=10,安排在同一排编号相邻的座位，则应该安排在编号最小的相邻座位
			{
				k=j-p+1;//k=6
				int d;
				for(d=k;d<=j;d++)//6 7 8 9 10
				{
					if(a[d]==0)
					{
						a[d]=1;
						cout<<d<<" ";
					}
				}
				cout<<endl;
				break;
			}
			else if(j==100)//没有连坐的位置了,应该安排在编号最小的几个空座位中
			{
				sum=0;
				for(k=1;k<=100;k++)
				{
					if(a[k]==0&&sum<p)
					{
						a[k]=1;
						cout<<k<<" ";
						sum ++;
					}
					if(sum>=p)
					{
						cout<<endl;
						break;
					}
				}
			}
		}
	}
}
/*
样例：
23
4 2 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4 5
输出
1 2 3 4
6 7
11 12 13 14
16 17 18 19
21 22 23 24
26 27 28 29
31 32 33 34
36 37 38 39
41 42 43 44
46 47 48 49
51 52 53 54
8 9
56 57 58 59
61 62 63 64
66 67 68 69
71 72 73 74
76 77 78 79
81 82 83 84
86 87 88 89
91 92 93 94
96 97 98 99
5 10 15 20
25 30 35 40

输入
26
4 4 1 5 2 2 4 2 2 1 3 5 3 3 4 5 4 3 4 5 5 2 2 2 2 5
输出
1 2 3 4
6 7 8 9
5
11 12 13 14 15
16 17
18 19
21 22 23 24
26 27
28 29
10
31 32 33
36 37 38 39 40
41 42 43
46 47 48
51 52 53 54
56 57 58 59 60
61 62 63 64
66 67 68
71 72 73 74
76 77 78 79 80
81 82 83 84 85
34 35
44 45
49 50
69 70
86 87 88 89 90
*/