2020年“联想杯” A Archmage 题解

题目大意

你有初始的n点法力值，有m个回合，在回合初，你可以花费x点法力值，制造一个水球，在回合结束时，你可以回复y点法力值。问最多水球数量。

解题思路

哇。。这个是真的卡了我好久。。

一直没想到正确的思路。。

结果一看题解。。

我们首先可以分两种情况。

1、$y\ge x$

显然，每回合回复的法力值都足够消耗，答案显然是m。

2、$y<x$

这里很难想。

我刚开始想的时候，是想到答案为$(n+m*y)/x$,后来发现不对，就没往这方面想了。

结果是$(n+(m-1)*y)/x$。

对于每一回合来说，我上回合回复的y，我之后的回合总能够使用到，但是我第m回合的时候，回复的法力值相当于是无用的，所以实际上增加的应该是$(m-1)*y$。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		ll n, m, x, y;
		cin >> n >> m >> x >> y;
		if (y >= x) {
			cout << m << endl;
			continue;
		}
		ll ans = (n + (m - 1) * y) / x;
		ans = min(ans, m);
		cout << ans << endl;
	}
}