CF1399E2 Weights Division (hard version) 题解

AbsMatt · 2023-12-29 15:14:04 · 题解

题目传送器

Easy Version

更爽的阅读体验

Easy Version solution

CF 2200

题意

翻译讲的很清楚了，这里就不多展开了。

做法

Easy Version 保证了边权的花费为 1，所以直接丢进大根堆然后贪心就行了。但是本题的边权花费为 1 或 2，如果直接将边权为 2 的贡献 \times 2 会 Wrong answer on test 21，给一个 Hack。

input：
1
3 10099
1 2 10000 2 
1 3 100 1

ans：
1

Hack by dead_X

此时还想贪心就变得非常困难，所以可以思考将答案划分成选择边权花费为 1 的答案 + 选择边权花费为 2 的答案。当只选择边权花费为 1 的答案时，可以确定操作的顺序（即 Easy Version），同理，只选择边权花费为 2 的答案也可以提前处理操作顺序。

然后只要枚举要操作花费为 1 的次数，并计算花费为 2 的次数即可。此时的时间复杂度为 O(n^2\times \log n)，无法通过此题。只需将计算花费为 2 的次数用双指针优化掉即可，时间复杂度为 O(n \times \log n)，记得处理操作全是花费为 1 和 2 的答案，开 long long。

AC Code