H. Rikka with A Long Colour Palette

# 2018 ICPC 徐州区域赛 H Rikka with A Long Colour Palette

题目链接：[http://codeforces.com/gym/102012/problem/H](http://codeforces.com/gym/102012/problem/H)
![在这里插入图片描述](https://pic.lass.work/i/2024/05/27/x7rrye-0.bmp)

## 题意

有n条线段[l,r]，k种颜色，为每条线段染一种颜色，问能被k种颜色覆盖的区间的最大总长，并输出一种染色方案。
∑n<=2e6，1<=k<=2e5，0<=l<r<= 1e9。

## 思路

贪心+扫描线
如果某一段>=k条的线段覆盖，那么这一段一定是满足条件的，问题在于如何求染色方案。
把 n 条线段的 2 * n 个端点按位置排序，相同位置右端点更靠前 （因为右端点归还颜色要先于左端点染色），将左端点标记为1，右端点标记为-1。
用一个队列 col 存待使用的颜色，开始时存入1 ~ k。
从小到大遍历排序后的端点，

如果是左端点，并且 col 队列不为空，我们就将这个线段染成队首的颜色.

如果是左端点，并且 col 队列为空，随便染色会有后效性，于是将这条线段存入延迟染色集合set中；

如果是右端点，如果这条线段染过色，就将该颜色放入队尾，进行回收

如果是右端点，如果这条线段没被染色，那么它一定在延迟染色集合set里，没有贡献，染什么色都可以，就染成1，然后从延迟染色集合中去掉。

处理完该端点后，若 col 不空, 即覆盖的颜色不够k 种，则从set 中取出延迟染色的线段为其分配颜色，直到两者其中一个为空。

至于总长度，记录一下col 由不空变为空的位置st，由空变为不空的位置ed.
st 与 ed 之间的这段都满足要求，将 ed - st 加到 总长度 sum 里

## 代码

```c++
#include<bits/stdc++.h>
#define buff  std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int N=2e5+10;
int t,n,k;
struct node
{
    int x,y,pos;
} a[N];
bool cmp(node a,node b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool book[N];
int ans[N];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(book,false,sizeof(book));
        scanf("%d%d",&n,&k);
        for(int i=1,p=1; i<=n; i++,p+=2)
        {
            scanf("%d%d",&a[p].x,&a[p+1].x);
            a[p].pos=a[p+1].pos=i;
            a[p].y=1;
            a[p+1].y=-1;
        }
        sort(a+1,a+n*2+1,cmp);
        queue<int> col;
        set<int> wait; 
        int sum=0;
        int flag=0,st=0;
        for(int i=1; i<=k; i++)
            col.push(i);
        for(int i=1; i<=2*n; i++)
        {
            if(a[i].y==1)
            {
                if(!col.empty())
                {
                    book[a[i].pos]=1;
                    ans[a[i].pos]=col.front();
                    col.pop();
                }
                else
                {
                    wait.insert(a[i].pos);
                }
            }
            else
            {
                if(book[a[i].pos])
                {
                    col.push(ans[a[i].pos] );
                }
                else
                {
                    wait.erase(a[i].pos);
                    ans[a[i].pos]=1;
                }
            }
            while(!col.empty()&&!wait.empty())
            {
                set<int>::iterator it=wait.begin();
                book[*it]=1;
                ans[*it]=col.front();
                col.pop();
                wait.erase(*it);
            }
            if(flag==0&&col.empty())
            {
                flag=1;
                st=a[i].x;
            }
            if(flag==1&&!col.empty())
            {
                flag=0;
                sum+=(a[i].x-st);
            }
        }
        printf("%d\n",sum);
        for(int i=1; i<=n; i++)
        {
            printf("%d%c",ans[i],(i==n?'\n':' '));
        }
    }
}

```

will us

H. Rikka with A Long Colour Palette

评论已关闭

分类

标签

归档

其它