[比赛][贪心][STL] codeforces1060D Social Circles

比赛结束智商上线系列

昨天的时候看C没整明白然后来看D，没想出来构造方法又回去卡C结果最后都没出呵呵呵，今早起来写了几个样例，组合了下就发现了规律：每次找到left最大的那个人和right最大的那个人，如果不是同一个人就合并中间left和right重合部分，ans加上这一部分（ans+=max(maxleft,maxright)）然后把这俩人重合的部分消去合并成一个新人放回集合里；如果是同一个人那就自己一个人一个圈子就好了。

感性理解的话就是要尽可能的让长的段之间有重复，重复就可以节省椅子，而始终都找最长的left和right就能保证这一要求。

wa点：multiset中如果两个元素它们定义<运算符的那个信息相同他就认为是相同的，而erase的时候会把所有相同的都erase掉，所以为了区别不同的人加上了一个id。。。很神奇吧。。

#include
//#include
//#include

using namespace std;

typedef long long LL;
const int maxn=2e3+5;
const int mod=1e9+7;

struct node1
{
    int id,l,r;
    node1(){id=l=r=0;}
    node1(int id,int l,int r):id(id),l(l),r(r){}
    bool operator< (const struct node1 & rhs)const
    {
        if(l!=rhs.l)
            return l>rhs.l;
        else
            return idrhs.r;
        else
            return id LS;//error?
multiset RS;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL ans=0;
    int n,l,r;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>l>>r;
        LS.insert(node1(i,l,r));
        RS.insert(node2(i,l,r));
    }
    int cnt=n+1;
    node1 t1;
    node2 t2;
    while(!LS.empty())
    {
        t1=*LS.begin();
        t2=*RS.begin();
        RS.erase(RS.begin()),LS.erase(LS.begin());
        if(t1.id!=t2.id)
        {
            LS.erase(node1(t2.id,t2.l,t2.r));
            RS.erase(node2(t1.id,t1.l,t1.r));
            ans+=max(t1.l,t2.r);
            t1.id=cnt++;
            t2.id=t1.id;
            t1.l=t2.l,t2.r=t1.r;
            LS.insert(t1);
            RS.insert(t2);
        }
        else
            ans+=max(t1.l,t1.r);
    }
    cout<