[POJ][3829][模拟] Seat taking up is tough

题目大意

教室里有 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

发表回复取消回复