题解：P13849 [CERC 2023] Equal Schedules

· · 题解

具体思路

这道题的思路其实很简单，根据题意模拟即可。我们只需要看同一个人在新、旧名单中的工作时间差，也就是 \sum_{i=1}^{k}e_{i}-s_{i} ，然后再进行输出，就可以求得答案。

注意：如果一个人在任意名单里出现了，另一个名单里哪怕没有他也要计入答案。

代码实现

但是代码难写啊！我们可以尝试使用 2 个map去存储 2 个名单里每一个名字对应的工作时长。然后计算答案输出。

但这样有一个弊端，你需要先考虑旧名单里出现的，再去考虑 2 个名单里都出现的，以及只在新名单里出现的。这样会导致只在新名单里出现的相较于前两种情况晚输出，没办法满足按照字典序输出。

所以我们需要另一个map去存储答案，最后按序输出。

代码如下，里面有一些函数，我将会在文章末尾提供讲解

#include<bits/stdc++.h>
using namespace std;
map<string,int> mp1;//旧名单 
map<string,int> mp2;//新名单 
map<string,int> mp3;//答案
int tab[]={1,10,100,1000,10000};
int main()
{
    while(1)//输入旧名单 
    {
        string s;
        getline(cin,s);
        if(s=="------") break;//退出条件 
        int fst=s.find(" ");//分割点，也就是空格的下标 
        int snd=s.find_last_of(" ");
        int len=s.length();
        int x=0,y=0;//上下班时间 
        for(int i=fst-1,j=0;i>=0;i--,j++) x+=(s[i]-'0')*tab[j];//string转int 
        for(int i=snd-1,j=0;i>=fst+1;i--,j++) y+=(s[i]-'0')*tab[j];
        string s1=s.substr(snd+1,len-snd);
        mp1[s1]+=y-x;//插入进map 
    }
    while(1)//如上，输入新名单 
    {
        string s;
        getline(cin,s);
        if(s=="======") break;
        int fst=s.find(" ");
        int snd=s.find_last_of(" ");
        int len=s.length();
        int x=0,y=0;
        for(int i=fst-1,j=0;i>=0;i--,j++) x+=(s[i]-'0')*tab[j];
        for(int i=snd-1,j=0;i>=fst+1;i--,j++) y+=(s[i]-'0')*tab[j];
        string s1=s.substr(snd+1,len-snd);
        mp2[s1]+=y-x;
    }
    if(mp1.size()>mp2.size())//根据名单大小来遍历 
    {
        bool flg=0;//标记 
        for(auto i:mp1)
        {
            auto j=mp2.find(i.first);
            if(j!=mp2.end())//两个名单都有的 
            {
                if(mp2[i.first]-mp1[i.first]!=0)//如果有差异 
                {
                    mp3[i.first]=mp2[i.first]-mp1[i.first];//记录答案 
                    flg=1;
                }
            }
            else//只出现在旧名单 
            {
                mp3[i.first]=0-mp1[i.first]; 
                flg=1;
            }
        }
        for(auto i:mp2)
        {
            auto j=mp1.find(i.first);
            if(j==mp1.end())//只出现在新名单 
            {
                mp3[i.first]=mp2[i.first];
                flg=1;
            }
        }
        if(flg==0) cout<<"No differences found."<<endl;//无解 
        else//输出答案 
        {
            for(auto i:mp3)
            {
                if(i.second<0) cout<<i.first<<" "<<i.second<<endl;
                else cout<<i.first<<" +"<<i.second<<endl;
            }
        }
    }
    else//如上 
    {
        bool flg=0;
        for(auto i:mp2)
        {
            auto j=mp1.find(i.first);
            if(j!=mp1.end())
            {
                if(mp2[i.first]-mp1[i.first]!=0) 
                {
                    mp3[i.first]=mp2[i.first]-mp1[i.first];
                    flg=1;
                }
            }
            else
            {
                mp3[i.first]=mp2[i.first];
                flg=1;
            }
        }
        for(auto i:mp1)
        {
            auto j=mp2.find(i.first);
            if(j==mp2.end())
            {
                mp3[i.first]=0-mp1[i.first];
                flg=1;
            }
        }
        if(flg==0) cout<<"No differences found."<<endl;
        else
        {
            for(auto i:mp3)
            {
                if(i.second<0) cout<<i.first<<" "<<i.second<<endl;
                else cout<<i.first<<" +"<<i.second<<endl;
            }
        }
    }
    return 0;
}