TRZ_2007 的博客

TRZ_2007 的博客

题解 AT2331 【Restaurant】

posted on 2019-10-12 10:26:44 | under 题解 |

由于这道题目是一道数学题,于是自然是用数学方法来解决的了。

Description

给你一个数字 $n$ ,让你求出数字 $n$ 中有多少个15,记作 $b$ ,计算 $800 \times n$ - $200 \times b$ 。

Solution

这道题目其他都是简单的,就是我们求有多少个15应该怎么求呢?
我们来看看这个表:

数字 $n$ 拥有15的个数 $b$
1~14 0
15~29 1
30~44 2
…… ……

看出来了没有?如果数字 $n < 15 \times m$ ,则 $b = m-1$ 。
$m$ 怎么求呢?
我们有两种方法:

  • 1:枚举法
    枚举每一个可能的 $m$ ,如果满足条件就退出,时间复杂度为 $O(\frac{n}{15})$ 。
    再看看 $n$ 的数据范围:
    $$n \le 100$$
    水过……
  • 2:玄学
    在C++中,一个整数除以一个整数,商下取整。
    那么这样我们就不用枚举了!!时间复杂度降为 $O(1)$ 。

贴代码:

#include <cstdio>
#include <cmath>

int main()
{
    int a,b,n;
    scanf("%d",&n);
    a = n*800;
    b = (n/15) * 200;//直接水过,C++自带计算万岁!!
    printf("%d\n",a - b);
}