XDOJ1334

XDOJ1334

题目描述

这次数模校赛的B题是一道关于停车场的问题，tsy觉得这个很像一个小模拟，于是他对于智能停车场进行了构思，如果这个停车场能够在车辆进入的一刻就将停车的空位分配好，那么感觉这个停车场应该挺不错的。于是tsy指定了以下规则，每辆车给出一个到达时间和离开时间，当到了到达时间后，停车场自动为车辆分配一个较小编号的停车空位，当到达离开时间后，车辆离开，停车位重新成为空位。tsy为了研究停车场的空位分配情况，准备在给定每辆车的到来离开时间后计算出车辆停车的空位的编号情况，然而他算不出来，所以求助于你，你能帮帮他吗？

输入

单组数据
第一行一个数字C代表车辆的个数（1 <= C <= 1e3）
之后C行，第i行代表编号为i的车辆的进入和离开时间S和E（若同一时间有多车进入，优先分配编号较小的车的）
（0 <= S < E <= 1e3）
停车位的编号从1开始，并且停车位视为无限

输出

一行C个数字，第i个代表车辆i停车位的编号，数字间一个空格，行末不要有多余空格

样例输入

3
0 2
1 3
2 4

样例输出

1 2 1

题解

#include<iostream>
#include<cstring>
#include<algorithm>  
#define N 1010  
using namespace std;  
struct car 
{  
int arrive;  
int leave;
int park_num;
int index;
bool life;
}data[N];  
bool cmp(car x,car y)  
{
	if(x.arrive != y.arrive)	 	return x.arrive < y.arrive;
    else if(x.arrive == y.arrive)  		return x.index < y.index; 
	
}
bool cmp_dash(car x,car y)  
{
	return x.index < y.index;
}  
int main()  
{  
    int n;
    cin >> n;
    bool park[N];
    memset(park,0,sizeof(park));
    for(int i = 1 ; i <= n ; i++)  		cin >> data[i].arrive >> data[i].leave,data[i].index = i; 
    for(int i = 1 ; i <= n ; i++)		data[i].life = 1;
    sort(data+1,data+n+1,cmp);  
    for(int i = 1 ; i <= n ; i++)
    {
    	for(int j = 1 ; j < i ; j++)	if(data[j].leave <= data[i].arrive&&data[j].life)	park[data[j].park_num] =  0,data[j].life=0;
    	for(int j = 1 ; j <= n ; j++)
		if(!park[j])
		{
			park[j]++;
			data[i].park_num = j;
			break;
		}
	}
	sort(data+1,data+n+1,cmp_dash); 
	for(int i = 1 ; i < n ; i++)	cout << data[i].park_num << " ";
	cout << data[n].park_num;	
    return 0;  
}  

暑训选拔赛A题。笔者认为，本题核心为链式排序（即结构体与sort的结合应用）。遗憾地说，笔者在第一次做题时对题目理解有问题，输出时忽略了按照index的顺序进行输出。即便如此，仍被吐槽复杂度高，笔者承认，在遍历停车位时无效搜索过多，可能本题数据范围没有严格限制，本题仍能AC。一段时间后，笔者会对这种解法进行代码上的优化。

PS：第一次没有设结构体中的成员函数life，导致对已经用过并释放的停车位重复遍历，导致如果已经释放的停车位上有车，仍会以已经离开的车的时间比现有时间小为标准释放当前被占用停车位，最终导致错误。