[POI 2018] Prawnicy

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=5102

[算法]

首先，n条线段的交集一定是[Lmax,Rmin] ，其中，Lmax为最靠右的左端点，Rmin为最靠左的右端点

根据这个性质，我们不妨将所有线段按左端点为关键字排序，依次枚举最终交集的左端点，同时，我们还需维护一个小根堆，维护前k大的右端点，每次我们通过( 堆顶 - 当前枚举线段的左端点 )更新答案

[代码]

#include<bits/stdc++.h>

using namespace std;

#define MAXN 1000010

struct segment

{

        int id;

        int l,r;

} a[MAXN];

int n,k,ans,l,r,len;

priority_queue< pair<int,int> > q;

int res[MAXN];

template <typename T> inline void read(T &x)

{

    int f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline bool cmp(segment a,segment b)

{

        if (a.l == b.l) return a.r > b.r;

        else return a.l < b.l;

}

int main()

{

        read(n); read(k);

        for (int i = ; i <= n; i++)

        {

                a[i].id = i;

                read(a[i].l);

                read(a[i].r);

        }

        sort(a + ,a + n + ,cmp);

        ans = ;

        for (int i = ; i <= n; i++)

        {

                if ((int)q.size() < k)

                {

                        q.push(make_pair(-a[i].r,a[i].id));

                        if ((int)q.size() == k)

                        {

                                ans = max(ans,-q.top().first - a[i].l);

                                l = a[i].l; r = -q.top().first;

                                continue;

                        }

                } else

                {

                        if (a[i].r < -q.top().first) continue;

                        pair<int,int> tmp = q.top();

                        q.pop();

                        q.push(make_pair(-a[i].r,a[i].id));

                        if (-q.top().first - a[i].l > ans)

                        {

                                ans = -q.top().first - a[i].l;

                                l = a[i].l; r = -q.top().first;

                        }

                }

        }

        printf("%d\n",ans);

        if (ans == )

        {

                for (int i = ; i <= k; i++)

                        printf("%d ",i);

                printf("\n");

                return ;

        }

        for (int i = ; i <= n; i++)

        {

                if (a[i].l <= l && a[i].r >= r)

                {

                        res[++len] = a[i].id;

                        if ((--k) == ) break;

                }

        }

        for (int i = ; i <= len; i++) printf("%d ",res[i]);

        printf("\n");

        return ;

}

巴特西

[POI 2018] Prawnicy

最新文章

热门文章