题解：P13849 [CERC 2023] Equal Schedules

ryf2011 · 2025-08-26 16:35:41 · 题解

1.题目思路

简单的模拟题。

为了方便，我们用 \texttt{map} 分别记录两份排班表中每个人的值班时间总和，每次输入后直接在对应位置累加即可。

然而此时最终枚举人名是仍然不方便，所以我们可以再开一个 \texttt{vector} 记录所有不同的人名，这样就方便遍历了。

最后输出前，可以先对 \texttt{vector} 排序，这样就保证其按照字典序输出。输出时特判答案为正数的情况，先加 + 再输出即可。

如果遍历完成后都没有输出，则输出无解。

:::warning[map 的时间复杂度]{open} 是的，使用 \texttt{map} 的时间复杂度为 \mathcal O(\log n) 级别，在时限紧张的题目里请慎用它。 :::

2.本题的读入方式

本题建议使用快读进行读入，在码量较小的同时可以方便地处理读入。

原版的快读是这样的：

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

我们对第 3 行稍作修改，更改如下：

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') ff=true; //ff=true 表示第一份排班表读取结束
        else if(ch=='='){ //第二份排班表读取结束
            return -1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

由于本题不涉及读入负数，所以上述代码是正确的。

3.完整代码

注：本代码仅供参考。

#include<bits/stdc++.h>
using namespace std;
const int max_n=1005;
int s,e;
string t;
map<string,int> mp,mmp; //两份排班表
map<string,bool> vis; //判断该人名是否出现过
vector<string> names; //所有人名
bool ff,ot; //ff:第一份排班表是否输入完成；ot:是否有输出
inline int read(){ //快读
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') ff=true;
        else if(ch=='='){
            return -1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    while(true){
        s=read();
        if(s==-1){ //全部读入完成
            break;
        }
        e=read();
        cin>>t;
        if(!vis[t]){
            vis[t]=true;
            names.push_back(t);
        }
        if(ff){
            mmp[t]+=e-s; //第二份排班表
        }
        else{
            mp[t]+=e-s; //第一份排班表
        }
    }
    sort(names.begin(),names.end()); //按字典序排序
    for(string s:names){ //遍历
        if(mp[s]-mmp[s]==0){ //相等，跳过
            continue;
        }
        else{
            ot=true;
            cout<<s<<' ';
            if(mmp[s]>mp[s]){ //答案为正数
                printf("+%d\n",mmp[s]-mp[s]);
            }
            else{ //负数
                printf("%d\n",mmp[s]-mp[s]);
            }
        }
    }
    if(!ot){ //没有输出
        puts("No differences found.");
    }
    return 0;
}

题解：P13849 [CERC 2023] Equal Schedules

1.题目思路

2.本题的读入方式

3.完整代码

4.后记