比赛链接

2025牛客寒假算法基础集训营6

J.铁刀磨成针

题目描述

小鸡最近沉迷于【L2】传说中的刀贼卡组，该卡组秉承开局一把刀、输出全靠砍的思想，力求对敌方造成尽可能多的伤害。
一把刀初始攻击力为 ，接下来有 个回合，每回合按顺序包括以下两个阶段：
磨刀阶段：可以选择花费一单位磨刀石提升刀的攻击力一点（每回合最多一次）；
攻击阶段：可以选择攻击，会对敌方造成等同于刀攻击力的伤害、并使刀的攻击力减一（每回合最多一次）。刀的攻击力归零时会损坏、此后再也不能攻击。
假设初始磨刀石的个数是 ，给定 ，求最大造成的伤害。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：
第一行输入三个正整数 代表回合数、初始攻击力、初始磨刀石数量。

注意本题对多个测试文件的 之和没有额外的限制。

输出描述

对于每一组测试数据，输出一行一个整数，代表最大造成的伤害。

解题思路

首先，磨刀一定是从第一回合开始一直磨，直到磨刀石用完。

其次，砍的时间也应该是连续的，中间停止砍只会让总伤害减少。

因此，只需枚举开始砍的时间点即可，如果 ，则最晚应在 时间开始砍，在此之后砍只会让总伤害减少。

完整代码

#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

int n, x, y;

int dc(int a, int n) {
	return a * n - n * (n - 1) / 2;
}

static void solve() {
	int ans = 0;
	cin >> n >> x >> y;

	for (ll t = 1; t <= min(n, y); t++) { // 枚举开始时间
		ll tmp = 0;
		ll atk = x + t, s1 = min(n, y) - t; // s1：又磨又砍的时间
		tmp += atk * s1; // 又磨又砍的伤害
		tmp += dc(atk, min(atk, n - min(n, y) + 1)); // 只砍的伤害
		ans = max(ans, tmp);
	}

	cout << ans << endl;
}

signed main() {
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

如有错误欢迎指正~