1 条题解
-
0
何老师 (root) LV 0 MOD @ 2023-04-05 22:45:33
题意:给定序列h[1]..h[N],每次可以把相邻的两个元素都减少1,代价为2。要把序列所有元素变成相同,最小代价是多少?
贪心算法:
因为每次只能把相邻两个元素一起操作,所以按 h[2]..h[N] 依次考虑每个元素,把它们依次变成一样的值:
比如对于h[2],若h[2]<h[1],则就无解(因为h[1]只能与h[2]一起减少);若h[2]>=h[1],需要把h[2]减少成h[1],方法是(h[2],h[3])一起减少,代价为:2*(h[2]-h[1]),此时 h[2]变成h[1],h[3] 变成了 h[3]-(h[2]-h[1]);
接着,对于h[3],若h[3]<h[2],则把(h[1],h[2])一起减少成h[3],代价为2*(h[2]-h[3]);若h[3]>=h[2],需要把h[3]减少成h[2],方法是(h[3],h[4])一起减少,代价为:2*(h[3]-h[2]),此时 h[3] 变成 h[2],h[4] 变成了 h[4]-(h[3]-h[2]);
……
考虑 h[i],此时意味着h[1]..h[i-1]都变成一样的值,假设为 d。当 h[i] < d 时,若 i-1 是奇数,则无解;否则可以把 h[1]..h[i-1] 都变成 h[i],代价为2*(d-h[i])*(i-1)/2,此时 d=h[i];
当 h[i] >= d 时,需要把h[i]减少成d,方法是(h[i],h[i+1])一起减少,代价为:2*(h[i]-d),此时 d 不变,h[i+1] 变成了 h[i+1]-(h[i]-d);
……对于 i=2,3,4,…、N-1,处理完后,单独处理 h[N]:
若 h[N] < d,若 N-1 为奇数,则无解;否则可以把 h[1]..h[N-1] 都变成 h[N],代价为(N-1)*(d-h[N]),此时 d=h[N];若 h[N] > d 则无解(因为h[N]只能和h[N-1]一起变化)。
- 1