最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

2023牛客寒假算法基础集训营5

来源：博客园

2023牛客寒假算法基础集训营 5

部分题解: A B C D H K L


【资料图】

A

思路: 快排 + 前缀和 + 二分查找

先从小到大排序, 再求出排完序后的前缀和. 对于每次询问, 二分查找第一个大于 \(x\) 的数的下标\(cnt\), 那么区间的右边界 \(r = cnt - 1\) , 再和 \(k\) 比较判断, 得到区间的左边界 \(l = max(0, cnt - k)\) , 那么 \(ans = sum[r] - sum[l - 1]\)

A_小2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

B

思路:

每人都选最优的拿取方法使字典序最小, 那么就是每人每次只拿一个.

因为 \(小沙\) 是先手, 所以要么 \(小沙\) 比 \(小雅\) 多一个, \(小雅\) 赢; 要么一样多, 是平局.

B_2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

C

思路:

要判断每一种 \(p\) 序列情况下 \(a\), \(b\) 的大小值, 需要分情况讨论: (改变前为\(A, B\), 改变后为 \(a, b\))

  • \(A = B\), 无论 \(p\) 序列如何排列, 都会有 \(a = b\)

  • \(A \neq B\)

    • \(A\) 的位数 = \(B\) 的位数, 这种情况下, \(a\) 和 \(b\) 不会有恒定的 \(>\) 和\(<\)

    • \(A\) 的位数 \(>\) \(B\) 的位数

      输入可能会有前导零, 但即使没有前导零, \(p\) 序列也会使 \(A\) 和 \(B\) 出现前导零. 所以要把 \(A\) 和 \(B\) 相同的前几位去掉, 再进行判断

    • \(A\) 的位数 \(<\) \(B\) 的位数

      与上一点同理

C_2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

D

思路:优先队列, 每次合并区间更新各自所在关卡值, 并判断输出

D_2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

H

思路:模拟判断

H_2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

K

思路:

最优情况是每次取 \(x = \left \lfloor \frac{n}{2} \right \rfloor + 1\) , 循环遍历

K_2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

L

思路:

从 \(n\) 开始往 \(1\) 遍历, 每次都枚举 \(m\) 条指令, 对于每条指令下达后剩余的人数下, 在剩余相同的人数下取花费的最小值

L_2023牛客寒假算法基础集训营5 (nowcoder.com)

代码查看 (nowcoder.com)

关键词： 优先队列 进行判断