1.Teleporters（Hard Version）
- 题意：
有 n+2 个位置：0～n+1，给定n个数\(a_1\)～\(a_n\) ,有以下操作：
- 向左/右移动一格，代价为 1。
- 传送回 0 位置或者 n+1 位置，记你当前的位置为 i，则代价为\(a_i\)。每个位置只能发动一次传送。
求最大传送次数
- 思路：
因为每次传送都会回到0/n+1号点，所以，到达i点并传送的代价为 min{i,n+1-i}+\(a_i\) .
按照代价升序排序，从小到大取。
此时发现，第一次传送时，只能从0出发，会导致错误。
枚举第一个点为\(fir\)，代价为 \(fir\)+\(a_fir\) .
二分答案\(mid\)，表示传送\(mid+1\)次，此时总代价为：
- \(fir<mid\) \(:\) \((\sum_{i=1}^{mid}{min(i,n+1-i)+a_i} ) + fir+a_fir\)
- \(fir \geq mid\) \(:\) \((\sum_{i=1}^{mid+1}{min(i,n+1-i)+a_i} ) - min(fir,n+1-fir)+a_{fir} + fir+a_{fir}\)
判断即可
- 时间复杂度
排序： \(O(n log n)\)
枚举&二分 \(O(n log n)\)
\(O (n log n)\)
2.给树染色
- 题意：
一颗树有\(n\)个节点,点有点权.现要将这棵树染色，对于任意节点，在被染色之前它的父亲节点必须已经染上了色。
每次染色的代价为 \(T*A[i]\)，其中\(T\)代表当前是第几次染色。
求把这棵树染色的最小总代价。 - 思路：
将点权最大的点不断与其父节点合并，合并后新点点权为\(\sum_{i=1}^{n}{a_{N_i}}/n\)
证明合并后新点点权为\(\sum_{i=1}^{n}{a_{N_i}}/n\)：
设有两个已合并点级\(N,M\)。
- 交换前，染色代价为：
\(\sum_{i=1}^{n}{a_{N_i}*(T+i)}\) \(+\) \(\sum_{i=1}^{m}{a_{M_i}*(T+n+i)}\) - 交换后，染色代价为：
\(\sum_{i=1}^{n}{a_{N_i}*(T+m+i)}\) \(+\) \(\sum_{i=1}^{m}{a_{M_i}*(T+i)}\)
差为
\(\sum_{i=1}^{m}{a_{M_i}}*n - \sum_{i=1}^{n}{a_{N_i}}*m\)
大于零
\(\sum_{i=1}^{m}{a_{M_i}}*n > \sum_{i=1}^{n}{a_{N_i}}*m\)
\(\sum_{i=1}^{m}{a_{M_i}}/m > \sum_{i=1}^{n}{a_{N_i}}/n\)
故合并后点权为
\(\sum_{i=1}^{n}{a_{N_i}}/n\)
- 时间复杂度
set维护 \(O(n log n)\)