2020-2021:teams:manespace:2020_07_13_2020_07_19周报_week10
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:2020_07_13_2020_07_19周报_week10 [2020/07/13 09:04] iuiou 创建 |
2020-2021:teams:manespace:2020_07_13_2020_07_19周报_week10 [2020/07/18 10:30] (当前版本) intouchables [题目] |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ====专题==== | ====专题==== | ||
| - | [[动态规划]] | + | * [[动态规划]] 部分本周填坑 by iuiou |
| ====比赛==== | ====比赛==== | ||
| + | * [[atcoder beginner contest 173]] | ||
| + | * [[atcoder AIsing Programming Contest 2020]] | ||
| + | ====题目==== | ||
| + | * **题意**：有一些物品，现已知第i个物品放在前$k_i$位置时产生的贡献为$l_i$,否则产生的贡献为$r_i$，问如何排布才能使总贡献取到最大？ | ||
| + | | ||
| + | ***知识点**：stl，贪心，堆 | ||
| + | |||
| + | * **题解**：这题设计多条件限制最值。思路如下：首先可以将所有数分成两组，一组是满足l>r的，另一组是满足r>l的，显然第一组的物品尽量往前靠，后一组的物品尽量往后靠，其实两组通过划归可以归为一个问题，不妨考虑第一组，每个数都有基础贡献$r_i$,之后考虑$k_i$，k越小越要排前面，所以将第一组按照k的值排序，同时开一个小根堆维护l-r的值，遍历第一组的物品，一旦k的值小于堆的总量就插入，否则若k等于堆的总量，则比较l-r的值。这样最后将堆中的数加进答案即可。对于放后面的情况可以转化为前面的情况。总复杂度$O(n\log n)$ | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | =====恭天祥===== | ||
| + | |||
| + | ====专题==== | ||
| + | |||
| + | |||
| + | ====比赛==== | ||
| + | |||
| + | * [[atcoder AIsing Programming Contest 2020(QuantumBolt)]] | ||
| + | |||
| + | ====题目==== | ||
| + | |||
| + | |||
| + | |||
| + | =====刘怀远===== | ||
| + | |||
| + | 这位同志生病中，咕咕咕。 | ||
| + | ====专题==== | ||
| + | |||
| + | 无 | ||
| + | ====比赛==== | ||
| + | |||
| + | * [[Codeforces Round 656 (Div. 3)]] | ||
| + | ====题目==== | ||
| + | |||
| + | 也无 | ||
2020-2021/teams/manespace/2020_07_13_2020_07_19周报_week10.1594602268.txt.gz · 最后更改: 2020/07/13 09:04 由 iuiou
