东莞地产网站建设,简述建设iis网站的基本过程,罗湖在线,建e网灯具cf1561C. Deep Down Below
题意#xff1a;
有个英雄#xff0c;英雄有自己的力量值#xff0c;有n个洞穴#xff0c;每个洞穴有ki个怪物#xff0c;每个怪物有自己的血量#xff0c;当你力量值大于怪物血量#xff0c;你就杀死他#xff0c;否则你就失败#xff0c…cf1561C. Deep Down Below
题意
有个英雄英雄有自己的力量值有n个洞穴每个洞穴有ki个怪物每个怪物有自己的血量当你力量值大于怪物血量你就杀死他否则你就失败你每杀死一个怪物力量值1。如果你进了一个山洞就必须将山洞里所有怪物杀光才行。英雄可以按照任意顺序进入山东问打败所有怪物的最低力量值是多少
题解
山洞的进入顺序很重要我们应该进整体怪物比较弱的山洞相当于先练练级等力量值升高了再去挑战比较厉害的怪 对于山洞里的第j个怪血量是aj那我们要战胜这个怪最低需要攻击力aj1而他是这个山洞第j个怪说明我们会提升j-1个攻击力也就是我们需要aj-j2的攻击力进这个山洞才能战胜这个怪。我们求出所有山洞所需的最低攻击力然后排序这样就得到山洞的进入顺序。 进入一个山洞前我们就判断是否已有攻击力是否已经大于这个山洞的需求如果大于就计算通过山洞后的攻击力否则就对初始攻击力进行补充。 相当于我们维护了两个攻击力一个是初始攻击力也就是我们要输出的答案另一个是当前状态的攻击力表示当前攻击力情况用于判断是否可以通过接下来的山洞 详细看代码
代码
// 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 pairint, 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();
}
