F – The Union of k-Segments (前缀和更新)

  • 2019-02-09
  • 0
  • 0

题目链接:https://cn.vjudge.net/contest/281961#problem/F

题意:给你n个线段,输出覆盖k次以上的线段或者点。

思路:两个数组,一个数组表示线段,一个数组表示点,遍历一遍输出即可.

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int l,r;
}line[1000005];
int a[5000005],ls[5000005],b[5000005];
vector<node>ans;

bool cmp(node a,node b)
{
    return a.l<b.l;
}

int main()
{
    //ios::sync_with_stdio(false);
    int n,k;
    while(~scanf("%d %d",&n,&k))
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        ans.clear();
        int p=0;
        for(int i=1; i<=n; i++)
        {
            int l,r;
            scanf("%d %d",&l,&r);
            line[i]=node{l,r};
            ls[++p]=l;
            ls[++p]=r;
        }
        sort(ls+1,ls+p+1);
        p=unique(ls+1,ls+p+1)-(ls+1);
        for(int i=1;i<=n;i++)
        {
            int l=lower_bound(ls+1,ls+p+1,line[i].l)-ls;
            int r=lower_bound(ls+1,ls+p+1,line[i].r)-ls;
            a[l]++;
            a[r]--;
            b[l]++;
            b[r+1]--;
        }
        for(int i=1;i<=p;i++)
        {
            a[i]=a[i-1]+a[i];
            b[i]=b[i-1]+b[i];
        }
        for(int i=0;i<=p;i++)
        {
            if(a[i]>=k)//线段
            {
                int r=i+1;
                while(a[r]>=k&&r<=p)
                {
                    r++;
                }
                ans.push_back(node{ls[i],ls[r]});
                i=r-1;
            }
            if(a[i-1]<k&&a[i]<k&&b[i]>=k)//点
            {
                ans.push_back(node{ls[i],ls[i]});
            }
        }
        sort(ans.begin(),ans.end(),cmp);
        printf("%d\n",ans.size());
        for(int i=0;i<(int)ans.size();i++)
        {
            printf("%d %d\n",ans[i].l,ans[i].r);
        }
    }
    return 0;
}

评论

还没有任何评论,你来说两句吧