无标题文章

2017年 多校 第10 场 Schedule

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;
const int N=1e7+5;
typedef pair<int,int> P;
P a[N];
inline bool cmp(const P &a,const P &b)
{
    return a.second<b.second;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        multimap<int,int> Map;
        for(int i=0;i<n;i++)
        {
// second 开始时间  结束时间
            scanf("%d%d",&a[i].second,&a[i].first);
        }
// 开始时间优先
        sort(a,a+n,cmp);
        LL sum=0ll;
        for(int i=0;i<n;i++)
        {
            if(Map.size()==0)
            {
                Map.insert(a[i]);
            }
            else
            {
                map<int,int>::iterator it;
//第一个大于它
                it=Map.upper_bound(a[i].second);
                //printf("%d %d\n",it->first,it->second);
                if(it==Map.begin())
                {
                    Map.insert(a[i]);
                }
                else
                {
                     it--;
                     P tmp=make_pair(a[i].first,it->second);
                     Map.erase(it);
                     Map.insert(tmp);
                }
            }
        }
        map<int,int>::iterator it2;
        for(it2=Map.begin();it2!=Map.end();it2++)
            sum+=(it2->first) - (it2->second);
        printf("%d %lld\n",Map.size(),sum);
        Map.clear();
    }
    return 0;
}