P8344 题解

### 前言

题目传送门

\(\color{red}{see}\space \color{green}{in}\space \color{blue}{my}\space \color{purple}{blog}\)

这题作为本次比赛的 T1，难度感觉还行，算是一道结论题。

已经尽量讲得简单一些，没有用复杂的求和符号。

思路

很容易想到贪心策略，如下。

第 \(1\) 次放 \((z-1)\) 块银色木板，再放一块金色木板。

第 \(2\) 次放 \((z-2)\) 块银色木板，再放一块金色木板。

一直按照这个规律下去放木板，直到放完第 \(x\) 次。

注意，还有第 \((x+1)\) 次，这一步执行时已经没有金色木板了，但可以将剩下的空位都塞满银色木板，可以塞 \((z-x)\) 块。

因此，我们最终需要判断：\((z-1) + (z-2) + \cdots + (z-x) + (z-x)\) 是否大于等于 \(y\)。

循环暴力累加，时间复杂度是线性的，但我们需要让时间达到 \(O(1)\)。

化简这个算式即可： \((z-1) + (z-2) + \cdots + (z-x) + (z-x)\)。

\(\begin{aligned}\text{原式} &= (x+1) \cdot z - (1 + 2 + \cdots + x + x)\\&= (x+1)\cdot z - \left[ \dfrac{(x+1)\cdot x}{2} + x \right]\end{aligned}\)

这就是本题结论了。

坑点

切记开 long long。

开始时还需要判断一下，如果 \(x > z\) 就必定无解。

完整代码

#include <iostream>
#include <cstdio>
using namespace std;
bool solve()
{
	long long x, y, z;
	scanf("%lld%lld%lld", &x, &y, &z);
	if (x > z) return false;
	return ((x+1) * z - (x * (x+1) / 2 + x) >= y);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		bool t = solve();
		if (t) puts("Renko");
		else puts("Merry");
	}
	return 0;
}

首发：2022-05-17 17:37:47