### 前言
\(\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
标签:return,木板,color,题解,long,cdot,cdots,P8344 From: https://www.cnblogs.com/liangbowen/p/16622876.html