Codeforces Round #740 C. Deep Down Below

题目链接

题意

有 n n n个洞穴，每个洞穴有 k i k_i ki​个怪物，每个怪物都有一个防御力 a i , j a_{i,j} ai,j​

英雄有一个初始攻击力 S S S，当英雄的攻击力严格大于怪物的防御力时英雄可以击杀怪物，英雄击杀怪物时攻击力会加 1 1 1

英雄可以选择一个洞穴从头到尾击杀这个洞穴的所有怪物，如果不能击杀则游戏结束

问英雄的初始攻击力最小值是多少时英雄可以杀掉所有怪物

思路

设英雄进入洞穴时攻击力为 S S S，当打到第 j j j个怪物时攻击力为 S + j ( j > = 0 ) S+j(j >= 0) S+j(j>=0) 所以只需要求出 每个洞穴的 m a x ( a i , j − j ) + 1 max{(a_{i,j}-j)+1} max(ai,j​−j)+1即为英雄进入该洞穴的初始攻击力最小值

我们肯定先攻击 m a x ( a i , j − j ) + 1 max{(a_{i,j}-j)+1} max(ai,j​−j)+1最小的洞穴（打怪升级再打boss），所以只需要对 m a x ( a i , j − j ) + 1 max{(a_{i,j}-j)+1} max(ai,j​−j)+1排序后遍历即可

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return f * x;
}
pair<ll,ll> maxi[100005];
ll a[100005];
void solve() {
    int n = read();
    for (int i = 0; i < n; ++i) maxi[i].first = 0;//英雄进攻改巢穴需要的最小攻击力
    for (int i = 0; i < n; ++i) {
        int k = read();
        maxi[i].second = k;
        for (int j = 0; j < k; ++j) {
            a[i] = read() - j + 1;
            maxi[i].first = max(maxi[i].first, tmp[j]);
        }
    }
    sort(maxi, maxi + n);
    ll now = 0,tmp = 0;//所需最小攻击力   打怪后加的攻击力
    for (int i = 0; i < n; ++i) {
        if (now + tmp < maxi[i].first) now = maxi[i].first - tmp;
        tmp += maxi[i].second;
    }
    cout << now << endl;
}

int main() {
    int _;
    cin >> _;
    while (_--) solve();
    return 0;
}