CF1561C 题解

link

hzy 有一个力量值，有 $n$ 个洞穴，hzy 可以以任意顺序探索洞穴，探索时一个洞穴不能必须打完里面的怪物才能去探索另外的洞穴。

第 $i$ 个洞穴里有 $k_i$ 个怪物，hzy 必须按顺序打这 $k_i$ 个怪物。hzy 的力量必须严格大于怪兽的防御值 $a_{i,j}$，才能打败这个怪兽，打败一个怪兽后 hzy 的力量值会加 $1$。问 hzy
刚开始至少有多少力量才能探索完所有洞穴。

$1 \le n \le 10^5$，$1 \le \sum k_i \le 10_5$，$1 \le a_{i,j} \le 10^9$。

显然这题要用 useful 的算法！

对于每个洞穴，我们记两个值，探索完后 hzy 可以增加的力量值和最少需要多少力量值才能探索完。后者可以用 $k_i\log k_i$ 的二分答案求出。

对于 $n$ 个洞穴按照最少需要的力量值排序，然后再次二分，这次直接二分询问的答案。

总时间复杂度 $O(n\log n + \sum k_i \log k_i)$

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}

#define N 100010
#define INF (1000000010)
#define fi first 
#define se second

int n, b[N];
pair<int, int> a[N];

bool check(int x) {
    for (int i = 1; i <= n; i ++) {
        if (a[i].fi > x) return false;
        else x += a[i].se;
    }
    return true;
}
bool check1(int x, int n) {
    for (int i = 1; i <= n; i ++) {
        if (b[i] >= x) return false;
        else x ++;
    }
    return true;
}

int main() {
    for (int T = read(); T --;) {
        n = read();
        for (int i = 1; i <= n; i ++) {
            a[i].se = read(), a[i].fi = 0;
            for (int j = 1; j <= a[i].se; j ++) {
                b[j] = read();
            }
            int l = 0, r = INF;
            while (l + 1 < r) {
                int mid = l + r >> 1;
                check1(mid, a[i].se) ? r = mid : l = mid;
            }
            if (check1(l, a[i].se)) r = l;
            a[i].fi = r;
        }
        sort(a + 1, a + n + 1);
        int l = 0, r = INF;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            check(mid) ? r = mid : l = mid;
        }
        if (check(l)) r = l;
        printf("%d\n", r);
    }
    return 0;
}