cf1561C. Deep Down Below

題意：

有個英雄，英雄有自己的力量值，有n個洞穴，每個洞穴有ki個怪物，每個怪物有自己的血量，當你力量值大于怪物血量，你就殺死他，否則你就失敗，你每殺死一個怪物，力量值+1。如果你進了一個山洞，就必須將山洞里所有怪物殺光才行。英雄可以按照任意順序進入山東，問打敗所有怪物的最低力量值是多少？

題解：

山洞的進入順序很重要，我們應該進整體怪物比較弱的山洞，相當于先練練級，等力量值升高了，再去挑戰比較厲害的怪
對于山洞里的第j個怪，血量是aj，那我們要戰勝這個怪，最低需要攻擊力aj+1，而他是這個山洞第j個怪，說明我們會提升j-1個攻擊力，也就是我們需要aj-j+2的攻擊力進這個山洞，才能戰勝這個怪。我們求出所有山洞所需的最低攻擊力，然后排序，這樣就得到山洞的進入順序。
進入一個山洞前，我們就判斷是否已有攻擊力是否已經大于這個山洞的需求，如果大于就計算通過山洞后的攻擊力，否則就對初始攻擊力進行補充。
相當于我們維護了兩個攻擊力，一個是初始攻擊力，也就是我們要輸出的答案，另一個是當前狀態的攻擊力，表示當前攻擊力情況，用于判斷是否可以通過接下來的山洞
詳細看代碼

代碼：

// Problem: C. Deep Down Below // Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) // URL: https://codeforces.com/contest/1561/problem/C // Memory Limit: 512 MB // Time Limit: 2000 ms // Data:2021-08-24 23:31:32 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef LOCALstartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef LOCALendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 2e5; int a[maxn]; int tot[maxn]; struct node {int id, maxx; } w[maxn]; bool cmp(node a, node b) {if (a.maxx == b.maxx)return tot[a.id] > tot[b.id];//山洞怪物數量多的elsereturn a.maxx < b.maxx;//血量排序 } int main() {//rd_test();int t;read(t);while (t--) {int T;read(T);for (int i= 1; i <= T; i++) {read(tot[i]);w[i].id= i;for (int j= 1; j <= tot[i]; j++) {read(a[j]);w[i].maxx= max(w[i].maxx, a[j] - j + 2);//所需要的最低攻擊力}}sort(w + 1, w + 1 + T, cmp);int tmp= tot[w[1].id] + w[1].maxx;//tot[]為可以提升的攻擊力int ans= w[1].maxx; //起初攻擊力for (int i= 2; i <= T; i++) {if (tmp >= w[i].maxx) {tmp= tmp + tot[w[i].id];}else {ans= ans + w[i].maxx - tmp;tmp= w[i].maxx + tot[w[i].id];}}cout << ans << endl;for (int i= 1; i <= T; i++) {w[i].id= 0;w[i].maxx= 0;tot[i]= 0;}}return 0;//Time_test(); }

總結

以上是生活随笔為你收集整理的cf1561C. Deep Down Below的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。