P8344 solution

RNTBW · 2022-05-14 18:24:26 · 题解

这是结论题？

看起来像贪心吧...

题意

• 有 x 个金色木板，y 个银色木板和一个能放下 z 个木板的桶，当在桶内放下一个金色木板后桶内的银色木板会消失，问是否能使所有木板都进入过桶。

思路

看一下样例就知道，y 非常的大。

所以我们就有了一个思路：将能放银色木板的最大数量计算出来再与 y 比较。

怎么计算呢？

贪心！

我们要放最多的银色木板，而在放一个金色木板后所有的银色木板会清零。

那么？ 自己思考两分钟

恍然大悟：

我们可以最大化利用桶的容积，放最多的银色木板，最后放一个金色木板将其清零！

当然这里还有几个坑点：

• 最多的银色木板数量是 z-1 而不是 z。

• 放了一个金色木板后 z 要减一。

• 在循环完之后桶内还有一些剩余空间也要算！

于是思路就出来了：

循环 x 次（有 x 个金色木板，也就有 x 次清零的机会），每次将 z 减一，同时累加器 k 加上 z。

最后将 k 与 y 进行比较。

好了，代码打出来了，样例过了，应该可以...

#include<bits/stdc++.h>
using namespace std;
long long t,x,y,z,i,k;
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&x,&y,&z);k=0;
        if(x>z)
        {puts("Merry");continue;
        }
        if(x+y<=z)
        {puts("Renko");continue;
        }//两种特判
        while(x) z--,x--,k+=z;
        if(k+z<y)puts("Merry");
        else puts("Renko");
    }
    return 0;
}

70 分...

老规矩，开始优化！

我们想到，可以将循环中的 z 放入一个 a 数组中，

然后求 \sum_{i=1}^x a_i 即可。

似乎没用

但是！

仔细想，a 数组满足什么？

由于我们的 z 在循环内是每次恒定减一的，所以...

这个数组满足单调递减！

那么再求 \sum_{i=1}^x a_i 就可以用等差数列优化！

小学就学过的等差数列求和公式就不用多说了吧。

当然我在这儿用的是平均数 \times 项数，也是可以滴~

啊还有一个坑点：

• 当 x 是 2 的倍数时平均数要加 \dfrac{1}{2}。

事已至此，万事大吉，可以...

不要紧张，100 分拿到手！

#include<bits/stdc++.h>
using namespace std;
long long t,x,y,z,k;
long double s;//血泪教训！
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&x,&y,&z);//血泪教训！
        if(x>=z)
        {puts("Merry");continue;
        }
        if(x+y<=z)
        {puts("Renko");continue;
        }
        s=z-1-x/2+(x%2 ? 0:0.5);
        //平均数
        k=x*s;//总和
        if(k+z-x<y)puts("Merry");
        //z-x是剩余的空间
        else puts("Renko");
    }
}

完结撒花~