2020-2021:teams:manespace:codeforces_round_643_div2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:manespace:codeforces_round_643_div2 [2020/05/25 20:28] iuiou 创建 |
2020-2021:teams:manespace:codeforces_round_643_div2 [2020/05/26 11:57] (当前版本) iuiou [E] |
||
|---|---|---|---|
| 行 152: | 行 152: | ||
| ===== E ===== | ===== E ===== | ||
| - | 题意：给定一个序列，有三种操作，第一种以a为代价让序列中一个数-1，第二种操作为以b为代价让序列种一个数+1，第三种操作是以c为代价让一个数+1，同时让一个数-1。问要将序列中所有数都变成一样的最少需要花费多少代价。 | + | 题意：给定一个序列，有三种操作，第一种以$a$为代价让序列中一个数-1，第二种操作为以$b$为代价让序列种一个数+1，第三种操作是以$c$为代价让一个数+1，同时让一个数-1。问要将序列中所有数都变成一样的最少需要花费多少代价。 |
| - | 题解：首先和容易想到枚举最终的数，肯定不能暴力枚举，所以要考虑答案随最终的数变化的轨迹，发现如果最终高度很小，则花费很大，最终高度很大，花费同样很大，最小值一定在中间某点取得，而且变化近似为二次曲线关系，则容易想到三分法，现在考虑给定高度，计算花费，首先可以意识到一点，一次第三种操作可以抵消一次第一，二种操作，接下来只要比较a+b和c哪个大，即可解决问题。 | + | 题解：首先和容易想到枚举最终的数，肯定不能暴力枚举，所以要考虑答案随最终的数变化的轨迹，发现如果最终高度很小，则花费很大，最终高度很大，花费同样很大，最小值一定在中间某点取得，而且变化近似为二次曲线关系，则容易想到三分法，现在考虑给定高度，计算花费，首先可以意识到一点，一次第三种操作可以抵消一次第一，二种操作，接下来只要比较$a+b$和$c$哪个大，即可解决问题。 |
| <hidden> | <hidden> | ||
2020-2021/teams/manespace/codeforces_round_643_div2.1590409729.txt.gz · 最后更改: 2020/05/25 20:28 由 iuiou
