1. 题目

传送门= ̄ω ̄=

2. 题解

又用STL水了一题啊!呜呼!

其实还是有点思维的,就是你要记得:之前留下来的区间必然不重叠!

当读入一个新的预约时,不断查找已经存在的预约中end值大等于新预约start值,并且最接近该start值的预约,找到一个删除一个,直到不能删除为止。因为不冲突的预约都是不相互覆盖的,所以它们的start值与end值必然是递增序列,所以一旦一个预约不能删除,后面的预约也不能删除。

以上摘自LUOGU一篇题解

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
int n,sta,end,ans,tot;
char opt[5];
multimap<int,int> t;
int main()
{
    IN(n);
    while(n--)
    {
        scanf("%s",opt);
        if(opt[0]=='A')
        {
            IN(sta),IN(end),tot=0;
            while(!t.empty())
            {
                multimap<int,int>::iterator i=t.lower_bound(sta);
                if(i->second>end||i==t.end())break;
                t.erase(i),tot++,ans--;
            }
            t.insert(make_pair(end,sta)),printf("%d\n",tot),ans++;
        }
        else printf("%d\n",ans); 
    }
    return 0;
} 
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *