题解：P17600 「RiOI-8」城ケ崎 ノア

· · 题解

发现性质，两行相邻必有交，为什么呢？假设两行相邻没有交，我们并到一行，不劣。

所以我们的思路就是把这些区间划分到最少个没有交的集合，这个很经典了，按 r 排序。

之后对当前所有集合的最右端点开 set，能插入就插入，插入不了就新开一个集合。

发现不同区间右端点可以重合，所以右端点相同要按照左端点排一下，我因为这个 WA 了好几次。

怎么计算答案？发现一个集合里有 \ge 2 个区间，我们一定不会让它和别的集合相邻，因为区间总共有 n 个，我们每次把这种大的集合贴边放就行了，一定可以这么构造。

所以可能相邻的集合一定是大小为 1 的，并且由于不能合并，一定会产生恰好为 1 的丑陋值。

可以参考一下样例 2，很好的例子。

所以可以对大小为 1 的集合和大小 \ge 2 的集合分别开 set。

你可能会问，如果能插入现有的集合，是优先插入大小为 1 的还是优先插入 \ge 2 的？

实际上都可以，举个例子，假设一共 8 个区间，我们按照上面的两种方式，分别能合出来 2,2,1,1,1,1 和 3,1,1,1,1,1 这两种，也就是 4 个 1 放在 4 个格子里或 5 个 1 放到 6 个格子里，都会产生 3 的丑陋值。

这个不仅证明了插入是任意的，而且还可以进一步推广得到 1 怎么放，设有 g 个 1 和 h 个格子，那么有 h - g 个格子可以不放，会减少 1 的丑陋值，所以最后答案为 g - 1 - (h - g) = 2g - h - 1。

现在答案求出来了，还要构造方案，这个就比较简单了，实现方法就是 set 里面存一个 id，然后插入元素就放到对应的 vector 里，多测要清空。

我的代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N = 200010;
int T,n,idx;
struct node{
    int l,r,id;
}a[N];
bool cmp(node x,node y){
    if(x.r != y.r)return x.r < y.r;
    else return x.l < y.l;
}
int ans[N];
vector<int> e[N];
multiset<pii> s1,s2;
void solve(){
    idx = 0;
    s1.clear() , s2.clear();
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].id = i;
    }
    sort(a + 1 , a + n + 1 , cmp);
    for(int i = 1;i<=n;i++){
        if((!s1.empty()) && (*s1.begin()).first < a[i].l){
            int id = (*s1.begin()).second;
            s1.erase(s1.begin());
            s2.insert({a[i].r , id});
            e[id].push_back(a[i].id);
        }else if((!s2.empty()) && (*s2.begin()).first < a[i].l){
            int id = (*s2.begin()).second;
            s2.erase(s2.begin());
            s2.insert({a[i].r , id});
            e[id].push_back(a[i].id);
        }else{
            s1.insert({a[i].r , ++idx});
            e[idx].push_back(a[i].id);
        }
    }
    int h = n - s2.size() * 2,now = 1;
    while(!s2.empty()){
        int p = (*s2.begin()).second;
        s2.erase(s2.begin());
        for(auto it : e[p])ans[it] = now;
        e[p].clear();
        now += 2;
    }
    int g = s1.size(),lft = h - g;
    cout<<max(0 , 2 * g - h - 1)<<"\n";
    while(!s1.empty()){
        int p = (*s1.begin()).second;
        s1.erase(s1.begin());
        for(auto it : e[p])ans[it] = now;
        e[p].clear();
        if(lft){
            now += 2;
            lft--;
        }else{
            now++;
        }
    }
    for(int i = 1;i<=n;i++)cout<<ans[i]<<" ";
    cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}