题目大意

教室里有 N*M 个座位，每个座位有一个“舒适值”。上课之前，有K个学生进入教室来占座。每个学生进入教室的时间都不同，且进入教室后会立马占座（忽略占座时间），每个学生都会按下述规则占座。

  • 每个学生会占T个座位，其中一个座位是自己的，其他是朋友的。
  • 学生会优先选择同一行相邻的T个座位占座，并且他会坐在最左边。
  • 如果有多个方案，那么他将选择能使自己“舒适值”最高的方案。
  • 如果没办法帮朋友占座，就只给自己占，并选择“舒适值”最高的座位。

根据所给条件，输出每个人自己占据的座位的坐标。

思路

比较水的模拟题，需要注意一点，输出每个学生占座结果的顺序应与学生信息的输入顺序相同。

代码

#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,k,map[30][30],mark[30][30],res[50][2];
//n行m列的教室，k个学生。
//map[][]用于记录座位舒适值。
//mark[][]用于记录某个座位是否已被占据。
//res[][]记录每个学生占据的自己的座位的坐标。 
struct point
{
	int hour;
	int minute;
	//hour、minute是每个学生进入教室的时间。 
	int total;
	int order;
	//order用来记录输入时给出的顺序，答案要按照输入顺序来输出。 
}student[50];
int cmp(const void* m,const void* n)
//按照进入教室的时间排序。 
{
	if((*(point*)m).hour==(*(point*)n).hour)
		return (*(point*)m).minute-(*(point*)n).minute;
	return (*(point*)m).hour-(*(point*)n).hour;
}
bool check(int x,int y,int z)
//判断从座位（x,y）开始，是否有z个连续的未被占据的座位。 
{
	if(y+z>m)
		return false;
	for(int i=0;i<z;i++)
		if(mark[x][y+i])
			return false;
	return true;
}
void solved(int x)
//模拟第x个学生占座。 
{
	int best_single=-1,best_group=-1;
	//best_single记录只能给自己占座时，单个座位能达到最高的舒适值。
	//为朋友占座时，自己座位能达到的最高舒适值。 
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		//遍历整间教室的座位。 
			if(!mark[i][j])
			//如果座位（i,j）没被占。 
			{
				if(best_group==-1&&best_single<map[i][j])
				//没有帮朋友占座的方案且当前座位的舒适值高于之前的其他座位。 
				{
					best_single=map[i][j];
					res[student[x].order][0]=i;
					res[student[x].order][1]=j;
				}
				if(best_group<map[i][j]&&check(i,j,student[x].total))
				//座位（i,j）符合条件，且属于自己的座位的舒适值高于之前的其他方案。 
				{
					best_group=map[i][j];
					res[student[x].order][0]=i;
					res[student[x].order][1]=j;
				}
			}
	if(best_group!=-1)
	//若存在帮朋友占座的方案。 
		for(int i=0;i<student[x].total;i++)
		//标记所占据的座位。 
			mark[res[student[x].order][0]][res[student[x].order][1]+i]=true;
	else if(best_single!=-1)
	//若存在帮自己占座的方案。 
		mark[res[student[x].order][0]][res[student[x].order][1]]=true;
		//标记所占据的座位。 
}
int main()
{
	while(scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				scanf("%d",&map[i][j]);
				mark[i][j]=false;
			}
		for(int i=0;i<k;i++)
		{
			scanf("%d:%d %d",&student[i].hour,&student[i].minute,&student[i].total);
			res[i][0]=res[i][1]=-1;
			student[i].order=i;
		}
		qsort(student,k,sizeof(student[0]),cmp);
		//按进入教室的时间顺序排序。 
		for(int i=0;i<k;i++)
			solved(i);
		for(int i=0;i<k;i++)
			if(res[i][0]!=-1)
				printf("%d %d\n",res[i][0]+1,res[i][1]+1);
			else
				printf("-1\n");
	}
}