题解

1 条题解

  • 0
    @ 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

信息

ID
2535
难度
9
分类
贪心 点击显示
标签
递交数
6
已通过
1
通过率
17%
被复制
2
上传者