Codeforces Round 931 (Div. 2)
比赛:Codeforces Round 931 (Div. 2)
A题:Too Min Too Max
标签: 构造算法(constructive algorithms)贪心(greedy)数学(math)
题目大意
- 对数组 a 找到四个不同下标 i, j, k, l ,最大化:
- |a
i−aj|+|aj−ak|+|ak−al|+|al−ai|
思路
- 因为选择四个数构成一个环,去相邻差值和,贪心四个值应该 大数 小数 大数 小数 交替摆放,可以证明这是最优的
- 一个数最多出现一次,所以找到最大,次大值,最小,次小值交替摆放即可
AC代码
1 |
|
B题:Yet Another Coin Problem
标签: 暴力枚举(brute force)动态规划(dp)贪心(greedy)数学(math)
题目大意
有 5 种不同的硬币,面额为1 3 6 10 15
找出所需的最少数量的这些硬币,使它们的总价值相加正好是 n (1 ≤ n ≤ 10^9^)
思路
- 贪心:1 3 6 10 15最大公约数是30,除了小于30的部分其他用15面额的硬币填充
- 小于30的部分用dp即可,完全背包问题。当然手动模拟也行反正没几项hh
- 选择n / 15 - 1个15面额的硬币,剩余钱数n%15+15 dp即可
AC代码
1 |
|
1 |
|
logo
1 |
|
1 |
|
Codeforces Round 931 (Div. 2)
https://leaf-domain.gitee.io/2024/03/02/cf-div2-931/