[仅作为参考] 算法游戏题解

寻宝游戏题解

1. 为了防止“剧透”，关键的部分被折叠起来了。

复制代码

这个问题很新o，是昨天的Codeforce在线赛的第二分区的A题（一般难度很低）https://codeforces.com/contest/2090/problem/A
这样的文字代表它可以被展开

1. NeverGonnaGiveYouUp

复制代码

朴素解法：

• 用代码模拟这个挖掘过程，在x和y挖完后判断是否达成了深度a
  

进阶解法：
点击查看进阶解法

• 一次性求得x与y在最后一轮挖掘前，的剩余深度，然后判断是否足够x有剩余的挖最后一次（被x挖完后如果有剩余，则说明y是最后一次挖掘）
  

代码与解释

朴素解法

假设我们先从朴素解法出发，因为这个解法不需要任何技巧，只是将操作流程转化为代码而已。
点击展开内容代码：

1. #include <cstdio> //c的标准输入输出头文件 (在.cpp中等效于 <stdio.h>)
3. int main()
4. {
5.     int n;
6.     scanf("%d", &n);
7.     while (n--)
8.     {
9.         int x, y, a;
10.         scanf("%d %d %d", &x, &y, &a);
11.         int leftToDig = a;
13.         while (true)
14.         {
15.             // X先挖
16.             leftToDig -= x; //待挖掘的深度被挖走X
17.             if (leftToDig + 0.5 < 0) //判断是否被Y先挖完
18.             {
19.                 printf("NO\n");
20.                 break;
21.             }
23.             // Y后挖
24.             leftToDig -= y; //待挖掘的深度被挖走X
25.             if (leftToDigeft + 0.5 < 0) //判断是否被Y先挖完
26.             {
27.                 printf("YES\n");
28.                 break;
29.             }
30.         }
31.     }
32. }

复制代码

上述代码是最朴素最基础的解法，

然而很不幸的是，如果在原判题平台上执行这段代码，会因为超时而无法通过大部分案例（最坏有\(O(n*a)\)的复杂度）



进阶解法

解决方案于是我们需要对操作进行简化：
不难发现，每一轮操作的起点都固定为x先开始，由y结束，而且每次判断退出的条件是一样的。
我们完全可以将两次判断合并成一次判断leftToDig -= (x+y)
然而还不够，这不会减少我们的循环体执行次数，我们需要一个更高效的方法处理这个事情
实际上，在这个十分漫长的判断阶段中，直到leftToDig接近x+y前，因为这个时候跳出条件(leftToDigeft + 0.5 < 0)一定不满足，循环体内部的语句起始都是无效的，

也就是说，实际上只有最末尾的部分（也就是leftToDig= x) //注意这里被我们替换成了求模版本的条件        {            printf("YES\n");        }        else        {            printf("NO\n");        }    }}[/code]Wow，代码段被瞬间简化了，时间复杂度也来到了\(O(n)\)范围内。
那为什么可以这么用呢？大家可能还记得小学二年级学习过的乘法，大概是这样引入的：

我们将 \((a+a+a+a+...+a) （假设一共加n次）\) 简化成 \((a \times n)\)

可以理解为，我们将多次相同的加法操作打包成为乘法

而除法作为乘法的逆运算，也有着类似的性质，也就是：将多次相同的减法操作打包成为除法操作

求模，是一种取余数的方式，也就是获得整数除法中被舍弃的部分的方式

或者换一个思路，我们在这里的运用方式，其实是获得多次相同减法操作后剩余的部分

而且十分“智能”的是，我们刚刚好可以获得最后一次能够完整减去(x+y)之后剩下的部分，就好像我们的leftToDig正正好小于(x+y)，一样，我们只需要考虑当前一轮中，x挖完后够不够y挖这一件事就可以了
于是循环体内部的复杂度被我们从 a 变成了 1,总复杂度就从 \(O(n*a)\) 变成了 \(O(n*1)\)

就可以通过啦
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！