贝壳找房 · 基础数学 · 算法编程题
贝壳找房 基础数学 时限 1 秒 / 256 MB

题目描述

牛客网即将通过投票选举新一代的牛王。
牛牛暗地里打听到，只要他的票数不少于L，那就一定会当选。
于是他开始拼命的进行拉票，已知开始时他有S张票，第二天，他的票数会变为 D2 = S × C + S ，第三天他的票数会变为 D3 = D2 × C + D2 ，以此类推
现在他想知道第D天，他的票数是否不少于L票

输入输出

输入描述
第一行一个整数T，表示测试数据组数
对于每组测试数据，输入四个整数，表示L, D, S, C
输出描述
输出共有T行
对于每组数据，若牛牛的票数不少于L，则输出YES，否则输出NO

样例共 1 组

样例 1 · 对于第一组数据，开始时有一张票，经过一天变为 1 + 1 × 1 = 2 张票，大于1，因此牛牛会成功 对于第一组数据，开始时有两张票，经过一天变为 2 + 2 × 1 = 4 张票，小于6，因此牛牛不会成功
输入
2
1 2 1 1 
6 2 2 1
输出
YES
NO

算法解析依据充分

考点：基础数学

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：基础数学

本题切入点

票数按倍数增长（D←D×C+D），增长极快，只需在不超过 L 的范围内递推并提前退出，注意用 64 位整数。

把题目转化为数学表达式，用公式或性质直接求值。

思路框架（基础数学 通法 · 非本题专属）

  1. 先写出题目要求的数学表达式或所求量的定义。
  2. 利用代数变形、不等式、函数单调性等性质化简。
  3. 按题面给的精度要求输出（浮点题注意误差）。
  4. 数据范围大时，往往存在 O(1) 或 O(log n) 的数学解，不必模拟。

实现要点：浮点输出通常要求相对误差不超过 1e-7，注意用 double/long double 或高精度小数。

复杂度：时间 O(1) ~ O(log n) ｜ 空间 O(1)

该范式的通法易错点

  • 整数除法丢精度；浮点比较直接用 == 。
  • 题目要求「相对误差」而非「绝对误差」，输出格式没对齐。

样例解读

样例 1：输入 2 / 1 2 1 1 / 6 2 2 1 → 输出 YES / NO

对于第一组数据，开始时有一张票，经过一天变为 1 + 1 × 1 = 2 张票，大于1，因此牛牛会成功

对于第一组数据，开始时有两张票，经过一天变为 2 + 2 × 1 = 4 张票，小于6，因此牛牛不会成功

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2024年秋招-贝壳找房-前端工程师-第二批笔试；2024年秋招-贝壳找房-测试开发工程师-第二批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解