[AGC040B]Two Contests

Description

给出若干条线段 \((L[i], R[i])\) ，把他们分成两个非空的集合，最大化集合内线段交的和。

\(n\le 10 ^ 5\)

Solution

考虑最小的一个右端点 p 和最大的一个左端点 q 。

讨论：

p 和 q 在同一集合内，那么选择一条除了这两条外最长的线段单独一个集合，剩下的和 p, q 一起一个集合。
p 和 q 不在同一集合内，那么考虑令 \(a_i = max(p - l_i+1， 0)， b_i = max(r_i - q + 1, 0)\) , 问题就转换成了把 {1,2...n} 划分成两个集合 \(S, T\) ，并且最大化 \(min\{a_i\} + min\{b_j\}\), \(i\in S, j \in T\)，可以把 \((a_i, b_i)\) 按 \(a_i\) 从大到小排序，然后 \(T\) 选的就是一段后缀。

code

#include <cstdio>

#include <cstring>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define End exit(0)

#define LL long long

#define mp make_pair

#define SZ(x) ((int) x.size())

#define GO cerr << "GO" << endl

#define DE(x) cout << #x << " = " << x << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

void proc_status()

{

	freopen("/proc/self/status","r",stdin);

	string s; while(getline(cin, s)) if (s[2] == 'P') { cerr << s << endl; return; }

}

template<typename T> inline T read()

{

	register T x = 0;

	register char c; register int f(1);

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

	while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));

	return x * f;

}

template<typename T> inline bool chkmin(T &a,T b) { return a > b ? a = b, 1 : 0; }

template<typename T> inline bool chkmax(T &a,T b) { return a < b ? a = b, 1 : 0; }

const int maxN = 1e5 + 2;

struct Info

{

    int a, b;

    bool operator > (const Info& B) const {

        return a > B.a;

    }

} info[maxN + 2];

int n, N;

int L[maxN + 2], R[maxN + 2];

void input()

{

    n = read<int>();

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

        L[i] = read<int>(), R[i] = read<int>();

}

int solve()

{

    int p = 1e9, q = 0;

    for (int i = 1; i <= n; ++i) chkmin(p, R[i]);

    for (int i = 1; i <= n; ++i) chkmax(q, L[i]);

    for (int i = 1; i <= n; ++i) info[i].a = max(p - L[i] + 1, 0);

    for (int i = 1; i <= n; ++i) info[i].b = max(R[i] - q + 1, 0);

    sort(info + 1, info + 1 + n, greater<Info>());

    static int suf[maxN + 2];

    suf[n + 1] = 1e9;

    for (int i = n; i >= 1; --i) suf[i] = min(suf[i + 1], info[i].b);

    int ans = 0;

    for (int i = 1; i <= n; ++i) chkmax(ans, max(p - q + 1, 0) + R[i] - L[i] + 1);

    for (int i = 1; i < n; ++i) chkmax(ans, suf[i + 1] + info[i].a);

    return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("xhc.in", "r", stdin);

    freopen("xhc.out", "w", stdout);

#endif

    input();

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

    return 0;

}

巴特西

[AGC040B]Two Contests

Description

Solution

code

最新文章

热门文章