题解：CF1621B Integers Shop

· · 题解

思路

后文中所用变量与原题面相同。

贪心是显然的。

发现如果要取尽可能多的数，那左端点要取前 s 个中最小的，右端点要取最大的。

不难发现，区间最多买两个。所以，分两种情况考虑：第一种是买了两个区间，一个包含最小值，一个包含最大值；第二种是只买一个区间，包含最小值和最大值。最后对答案取最小值。

AC Code

#include <bits/stdc++.h>
#define int long long
#define i64 long long
#define u64 unsigned long long
#define i128 __int128
#define u128 unsigned __int128
#define db double
#define pq priority_queue
#define mod 998244353
#define mod2 1000000007
#define pf1 push_front
#define pb1 push_back
#define pf2 pop_front
#define pb2 pop_back
#define inf 1073741823
#define INF 4611686018427387903
#define all(x) x.begin(), x.end()
using namespace std;
int T;

int n, ans, minl, maxr, minlc, maxrc, minall, l[100010], r[100010], c[100010];

inline void solve () {
    cin >> n, minl = 1 << 30, maxr = 0, minlc = maxrc = minall = 1ll << 60;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i] >> c[i];
        if (minl > l[i] && maxr < r[i])
            minl = l[i], maxr = r[i], minall = c[i], minlc = c[i], maxrc = c[i];
        else
            if (minl > l[i])
                minl = l[i], minlc = c[i], minall = 1ll << 60;
            else
                if (maxr < r[i])
                    maxr = r[i], maxrc = c[i], minall = 1ll << 60;
        if (minl >= l[i] && maxr <= r[i])
            minall = min(minall, c[i]), minlc = min(minlc, c[i]), maxrc = min(maxrc, c[i]);
        else
            if (minl >= l[i])
                minlc = min(minlc, c[i]);
            else
                if (maxr <= r[i])
                    maxrc = min(maxrc, c[i]);
        cout << min(minlc + maxrc, minall) << '\n';
    }
}
signed main () {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr), T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}