2023牛客寒假算法基础集训营4-清楚姐姐打怪升级

Solost

2023 年 01 月 30 日

238 次浏览

暂无评论

1145字数

题目题解

![2772997031.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/2772997031.png)

## solution

注意，怪物每秒都回血，但是攻击是每t秒才会攻击一次，如果血量一次秒不掉的话，每回合的攻击伤害小于等于回血量`vt`那么将永远杀不掉，输出-1；

求在第几回合k能杀了他，每次先砍一刀，如果一刀砍不死，那么就可以直接开始算了，那么就是`h - a + kvt <= ka`，化简后就是`k >= (h - v) / (a - vt)`向上取整，因为每个人都至少砍一刀,又因为能多砍几刀的人，所以在加上k，然后算出来了多少回合，再算秒数，考虑如果不能一刀秒杀，那么怪物必定会经过至少一次掉血+回血的循环。而最后一次击杀后，怪物立刻死亡肯定不会回血。每个怪物就需要k + 1次，最后的结果就是`(ans - 1) * t + 1`,因为最后一回合最后一刀砍死，然后只会多一秒，不会多一场的时间。

~~~cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

int main(){
	int n, t, a, f = 1;
	cin >> n >> t >> a;
	ll ans = n;
	for(int i = 1; i <= n; i++){
		int h, v;
		cin >> h >> v;
		if(h > a && v * t >= a)
			f = 0;
		if(h > a && f)
			ans += (h - a + (a - v * t - 1)) / (a - v * t);
	}
	if(f){
		cout << (ans - 1) * t + 1 << endl;
	}
	else{
		cout << "-1\n";
	}
	return 0;
}
~~~

最后修改：2023 年 02 月 02 日