题解 P8344 【「Wdoi-6」走在夜晚的莲台野】

chen_zhe · 2022-05-16 09:55:45 · 题解

显然，每次优先放入银色木板，到了最后一格的时候放入金色木板是最优的。根据这个思想去模拟放入过程，不开 long long 是 50-70 分，非常良心。

不妨考虑以最优情况放入所有金色木板后，所能承载的银色木板量。第一次放入金色木板前可以承载 z-1 块银色木板，第二次则是 z-2 块，以此类推到第 x 次则是 z-x 块，这构成一个等差数列。则可以通过放入金色木板而被挪出去的银色木板的总量为 \dfrac{(z-1+(z-x))\times x}{2} 块。放入最后一块金色木板之后，盒子还剩下 z-x 个空位可以放银色木板。故总共最多能放入 \dfrac{(2z-x-1)\times x}{2}+z-x 块银色木板，只需把 y 与之做比较即可。

计算过程要全程开 long long。数据我造的，被卡了的话请不要找我。

std：

#include <iostream>
using namespace std;
int main()
{
    long long T,x,y,z;
    cin >> T;
    while (T--)
    {
        cin >> x >> y >> z;
        if (x>z)
            cout << "Merry" << endl;
        else
        {
            long long tot=(z-1+(z-x))*x/2+z-x;
            cout << (tot>=y?"Renko":"Merry") << endl;
        }
    }
    return 0;
}