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;
}