acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(0)
  • 正经题解|听歌识曲

    模拟找歌曲的过程,用数组来存储信息。数组有两种表示形式,数组下标表示秒数,数组元素表示对应歌曲的编号,即 a[i]=xa[i]=xa[i]=x 表示第 iii 秒是第 xxx 首歌。这种存法的好处在于想找的时间能够直接找到对应歌曲编号,但需要大量的数组空间。题目中总时间可能会到达 101010^{10}1010 秒,所以这种存法只能通过部分测试点。 另一种存法是数组下标表示歌曲编号,数组元素表示当前歌曲的持续时间,即a[i]=xa[i]=xa[i]=x 表示第 iii 首歌持续 xxx 秒。 记录每首歌的持续时间,可以计算得到每首歌的结束时间。 当前歌曲结束时间=上一首歌的结束时间+当前歌曲持续时间。 因为只要找一首歌,所以用数组记录每首歌的结束时间,和前缀和的写法一样。找到第一个大于等于想找时间的结束时间,对应编号的歌名即为答案。 如果题目想要找多个时间对应的歌曲名,可以考虑二分的方法在前缀和数组中进行查找。

    userId_undefined

    AC君

    小有名气倔强青铜管理员
    17阅读
    0回复
    0点赞
  • <题解>

    #include <bits/stdc++.h> using namespace std; long long a[100010]; long long b[100010]; string s[100010]; int main() { long long n, m; cin >> n >> m; b[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i] >> s[i]; b[i] = b[i - 1] + a[i]; // 记录每首歌的结束时间 } }

    userId_undefined

    ‮

    倔强青铜时间刺客空间掌握者分治·分治练习生I/O·IO入门者
    5阅读
    0回复
    1点赞
首页