526互联

transform (牛客多校) (双指针+二分+ 中位数妙用+前缀和相减维护)

发布时间 2023-06-18 16:30:18作者: VxiaohuanV
题目大意:
  • n 个商店在 一条直线上,  有一个xi 然后 有 ai 个商品
  • 你可以把 商店的物品 移动到另一个商店, 代价为 : abs(xi-xj)
  • 在代价不超过T的情况下
  • 你可以选择一个商店来让 其他商店的物品都移到这个商店,问最多移动多少个物品

 

 

思路:

  • 双指针维护一个最大的区间, 因为这个最大区间的(中间商店选点,一定是物品数量的中位数那个商店)
  • 中位数二分, 代价利用前缀和相减维护即可