← 返回目录

算法笔试模拟题精解之“坏掉的时钟”

第 72 / 74 卷日期：

算法笔试模拟题精解之“坏掉的时钟”

贡献者 | 洪浩原

简介：本题关键在于理解题意。

题目描述

等级：容易

知识点：模拟

查看题目：坏掉的时钟

B 同学有一个时钟，能够显示 1-d，初始值为 1。这个时钟每天显示的数字加

一，特殊的，当某天显示的值为 d 时，第二天就会显示 1。

但是每个月的时间并不总是 d 天，因此 B 同学就要通过手动调整使得显示的时

间正确，每次手调都可以使显示数字加一。

现在给你 n 个月每月的天数，请你计算一下若是让时钟每天显示的数字都是正确

的，他这 n 个月一共需要调多少次时钟。

输入月份数 n（1 <= n <= 10^5）、时钟的最大显示时间 d（1 <= d <= 10^4）和

一个包含 n 个数的数组，第 i 个数表示第 i 个月有 ai 天（1 <= ai <= d）

输出使时钟正常显示一共要调整的次数。

示例 1

输入：

输出：

3

解题思路：模拟

本题关键在于理解题意：

题干的含义是，在除去最后一个月后，其余每个月的最后一天的 24 点时，时钟上

的逻辑时间会超过那个月的最大天数，同时实际时间变为下一个月的第 1 天。此时逻辑

时间和实际时间有差别，需要调整时钟，让逻辑时间重新回到 1，使其符合实际时间。

如题中例子所指：

3 5

[3, 4, 3]

  • 第 1 个月第 1 天，时钟实际值 1，符合；
  • 第 1 个月第 2 天，时钟实际值 2，符合；
  • 第 1 个月第 3 天，时钟实际值 3，符合；
  • 第 2 个月第 1 天，时钟实际值 4，不符合，对时钟进行 2 次加 1 操作，时钟实

际值变为 1，符合；

  • ......
  • 第 3 个月第 1 天，时钟实际值 5，不符合，对时钟进行 1 次加 1 操作，时钟实

际值变为 1，符合；

  • ......
  • 第 3 个月第 3 天，时钟实际值 3，符合；
  • 结束，共需要调整 3 次。

时间复杂度：O(n)

空间复杂度：O(1)

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”