题解：B4319 [语言月赛 202504] 礼堂预约

yummy · 2025-04-13 18:18:49 · 题解

本题考察日期计算和简单排序算法，对选手的阅读能力、分析能力、代码能力都有比较高的要求。如果选手没有采用合适的写法，可能会导致代码量增大。

首先，我们需要一个函数，计算当前日期，对应的第二天日期。因为这个过程涉及到数字加法，所以我推荐使用 int 存储，这样八位数 dt 对应的年、月、日就分别是 y=dt%10000,m=dt/100%100,d=dt%100。

为了计算 y 年 m 月的天数 maxd，我们可以用一个数组记录平年 12 个月的天数；然后如果是闰年 2 月，再额外加一天即可。

算好上述变量后，第二天可以按照如下流程计算：

• 通常情况下，y 年 m 月 d 日的第二天是 y 年 m 月 d+1 日。
• 但如果 d+1>maxd，那么答案是 y 年 m+1 月 1 日。
• 如果此时 m+1 是 13，那么就要变成 y+1 年 1 月。

该部分的代码如下：

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int tomorrow(int dt){
    int y=dt/10000,m=dt/100%100,d=dt%100;
    int maxd=days[m];
    if(m==2 && (y%4==0 && y%100!=0 || y%400==0))
        maxd=29;
    d++;
    if(d>maxd){
        d=1;
        m++;
    }
    if(m==13){
        m=1;
        y++;
    }
    return y*10000+m*100+d;
}

下一步我们考虑日程表的维护。预约在早上的活动最后一定在早上，下午、晚上类似，因此早上、下午、晚上是平行而独立的三个日程表，直接加一维数组，0 表示早上，1 表示下午，2 表示晚上即可。

为了更方便地比较活动类型的优先程度，可以规定 O,C,P 分别对应数字 0,1,2，这样，发生冲突时，类型更大的活动时间会被修改。

为了更方便地查找冲突的活动，我们可以规定日程表里所有活动按照举办时间的先后排序。具体地，act(tme,i) 表示 tme 时间（0,1,2 之一）、第 i 个举办的活动编号，而 cact(tme) 表示时间 tme 的活动个数。

int n,date[5005];
int type[5005];//0=O, 1=C, 2=P
int act[3][5005],cact[3];// 0=M, 1=A, 2=E
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s>>date[i];

        if(s[0]=='O')type[i]=0;
        else if(s[0]=='C')type[i]=1;
        else type[i]=2;

        cin>>s;
        int tme;
        if(s[0]=='M')tme=0;
        else if(s[0]=='A')tme=1;
        else tme=2;

        //插入新活动部分的代码，具体实现在下文提到
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",date[i]);
    return 0;
}

每次加入新活动时，使用类似插入排序的做法就可以保持数组的有序，具体地，假设要把编号 to_arr 的活动插入日程表，那么用一重循环 j 从 1 枚举到 cact(tme)：

• 如果 date_i > date_{act(tme,j)}，表示 i 的插入点在第 j 个活动之后，不需要处理。
• 如果 date_i<date_{act(tme,j)}，那么 i 应该插入在第 j 个活动之前，换言之 i 成为了第 j 个活动，而原来第 j 个活动成了需要插入的活动，代码中体现为 swap(act[tme][j],to_arr)。
• 如果二者相等，那么发生了一次冲突。此时比较二者谁的“权力”更大，如果 i 的“权力“更大，就把 act(tme,j) 这个活动从日程中拉出来（变成需要插入的活动）天数 +1，然后自己进去；否则自己天数 +1。

最后肯定剩下一个尚未插入的活动，直接安排到末尾即可。

        int to_arr=i;
        for(int j=1;j<=cact[tme];j++){
            int target=act[tme][j];//尝试把 to_arr 插入 target 所在位置
            if(date[target]==date[to_arr]){//活动撞了
                if(type[target]>type[to_arr] || type[target]==type[to_arr] && target>to_arr){
                    //to_arr 权力更大，从 target 位置拉下来
                    swap(act[tme][j],to_arr);
                }
                date[to_arr]=tomorrow(date[to_arr]);
            }
            else if(date[target]>date[to_arr])//正常插入排序
                swap(act[tme][j],to_arr);
        }
        cact[tme]++;
        act[tme][cact[tme]]=to_arr;