说明

该程序用于解决教室座位占座问题，根据学生到达时间和所需座位数量，按照特定规则分配座位。程序需要处理多个学生的占座请求，确保在满足连续座位需求的前提下，尽可能让学生获得舒适度最高的座位。

算法标签

• 模拟
• 排序
• 贪心算法

解题思路

1. 问题分析：教室座位排列成n行m列的网格，每个座位有唯一的舒适度指数。学生按到达时间顺序占座，优先选择连续且舒适度最高的座位。如果无法满足连续座位需求，则选择单个舒适度最高的座位。
2. 输入处理：读取教室的座位布局和学生的占座请求，直到遇到0 0 0结束。
3. 排序处理：按学生到达时间排序，确保先到先服务。
4. 座位分配：
   • 对于每个学生，检查是否有足够的连续座位满足需求。
   • 如果有，选择舒适度最高的连续座位组，并占用这些座位。
   • 如果没有，选择单个舒适度最高的座位。
5. 输出结果：按学生请求的顺序输出分配的座位坐标或-1（表示无法占座）。

分析

• 座位表示：使用二维数组a存储座位的舒适度指数，b数组记录每行剩余的座位数。
• 学生请求处理：按时间排序后，逐个处理学生的请求，确保公平性。
• 贪心选择：在满足连续座位需求时，优先选择舒适度最高的组合；否则选择单个最优座位。

实现步骤

1. 读取输入：读取教室的行数n、列数m和学生数k，然后读取座位舒适度指数和学生请求。
2. 排序学生请求：按到达时间排序，确保先到先服务。
3. 处理每个请求：
   • 检查是否有足够的连续座位。
   • 分配最优座位，并标记已占用的座位。
4. 输出结果：按原始请求顺序输出分配结果。

代码解释

• 数据结构：
  • a数组：存储座位的舒适度指数。
  • b数组：记录每行剩余的座位数。
  • t结构体：存储学生的请求信息，包括时间、所需座位数和分配结果。
• 排序函数：
  • cmp：按学生到达时间排序。
  • cmp1：恢复学生请求的原始顺序。
• 主逻辑：
  • 读取输入并初始化。
  • 排序学生请求。
  • 遍历每个请求，分配座位并更新座位状态。
  • 输出分配结果。

该程序通过有效的排序和贪心策略，公平且高效地解决了教室座位占座问题，适用于类似资源分配的场景。

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
int inf=99999999;
int a[40][40];
struct T
{
    int z,h,m,q,zx,zy,f;    //z表示提问顺序，最后按该值排序
};                    //f表示该占位同学能否找到一个位置
struct T t[60];
int cmp(struct T a,struct T b)
{    //先按照小时排，再按分钟排
    if(a.h<b.h)
    return 1;
    else if(a.h==b.h)
    {
        if(a.m<b.m)
        return 1;
        else
        return 0;
    }
    return 0;
}
int cmp1(struct T a,struct T b)
{
    return a.z<b.z;
}
int main()
{
    int i,j,k,l,m,n,b[60],qq;
    long long max;
    while(scanf("%d%d%d",&n,&m,&qq), n+m+qq != 0)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        for(j=1;j<=n;j++)                //表示该行还有几个座位
            b[j]=m;
        for(i=1;i<=qq;i++)
        {
            t[i].f=0;
            t[i].z=i;
            scanf("%d:%d%d",&t[i].h,&t[i].m,&t[i].q);
        }
        sort(t+1,t+qq+1,cmp);
        /*for(i=1;i<=qq;i++)
            printf("%d %d %d\n",t[i].h,t[i].m,t[i].q);*/
        for(l=1;l<=qq;l++)
        {
            max=-inf;
            int x;int y;
            long long sum;
            int s=0;
            for(i=1;i<=n;i++)
                if(b[i]==0) s++;
            if(s==n)
            {
                t[l].f=0;
                continue;
            }
            for(i=1;i<=n;i++)
            {
                sum=0;
                if(b[i]>=t[l].q)
                {
                    for(j=1;j<=m-t[l].q+1;j++)
                    {
                        sum=a[i][j];
                        for(k=j;k<j+t[l].q;k++)
                            if(a[i][k]==-inf) break;
                        if(k==j+t[l].q&&max<sum)
                        {
                            max=sum;
                            x=i;y=j;
                        }
                    }
                }
            }
            if(max==-inf)
            {
                int mx1=-inf;
                for(i=1;i<=n;i++)
                {
                    for(j=1;j<=m;j++)
                    {
                        if(mx1<a[i][j])
                        {
                            mx1=a[i][j];
                            x=i;y=j;
                        }
                    }
                }
                b[x]--;
                a[x][y]=-inf;
            }
            else
            {
                b[x]-=t[l].q;
                for(j=y;j<y+t[l].q;j++)
                    a[x][j]=-inf;
            }
            t[l].f=1;
            t[l].zx=x;
            t[l].zy=y;
        }
        sort(t+1,t+qq+1,cmp1);
        for(i=1;i<=qq;i++)
        {
            if(t[i].f)
            printf("%d %d\n",t[i].zx,t[i].zy);
            else
            printf("-1\n");
        }
    }
    return 0;
}