题目大意
教室里有 N*M 个座位，每个座位有一个“舒适值”。上课之前，有K个学生进入教室来占座。每个学生进入教室的时间都不同，且进入教室后会立马占座（忽略占座时间），每个学生都会按下述规则占座。
- 每个学生会占T个座位，其中一个座位是自己的，其他是朋友的。
- 学生会优先选择同一行相邻的T个座位占座，并且他会坐在最左边。
- 如果有多个方案，那么他将选择能使自己“舒适值”最高的方案。
- 如果没办法帮朋友占座，就只给自己占，并选择“舒适值”最高的座位。
根据所给条件，输出每个人自己占据的座位的坐标。
思路
比较水的模拟题，需要注意一点，输出每个学生占座结果的顺序应与学生信息的输入顺序相同。
代码
#include
#include
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");
}
}