牛客多校第二场 G transform

G transform

题意

在数轴上有n个箱子，第i个箱子里有ai$a_i$ 的货物，距离原点的距离是xi$x_i$, 移动一个货物从箱子i到j的花费是abs(xi−xi)$abs(x_i-x_i)$，要求在总花费 不超过 T的情况下把尽量多的货物移动到一个箱子里，求货物的最大数量ans

分析

前提
1. 首先来分析我们把货物移动到一个箱子，那么这些货物所在的区间一定是连续的区间，不可能是分立的，区间左端点或者右端点可能没有移动完.
2. 我们移动一个区间里的所有货物到一个箱子，这个箱子一定是区间货物个数中位数所在的箱子
第一个不解释了
关于第二个结论，我们可以看成是所有的箱子里都只有一个货物的推广，如果所有的箱子里都只有一个货物，那么肯定是放在区间中位数所在的地方最小，画个图大概就明白了

假设放在放在中位数的左边，则 花费的变化 =2∗(x[3]−x[2])−2(x[3]−x[2])+x[3]−x[2]=x[3]−x[2]$=2\ast (x[3]-x[2])-2(x[3]-x[2])+x[3]-x[2]=x[3]-x[2]$ 比原来增加了，在左边的时候同样，所以选在中位数的时候最小，然后推广一下就ok了
具体做法： 二分ans的值，枚举区间端点，然后求区间中位数就ok了
怎么快速求把区间所有货物都移动到某一点的花费呢

首先用sum$sum$记录前缀和
用sumd[i]$sumd[i]$记录把这些箱子都移到零需要的花费，
sumd[i]=sumd[i−1]+a[i]∗x[i];$sumd[i]=sumd[i-1]+a[i]\ast x[i];$
[l,r] 区间都转移到 l 需要的花费

cal(l,r)=sumd[r]−sumd[l]−(sum[r]−sum[l−1])∗x[l]$cal(l,r)=sumd[r]-sumd[l]-(sum[r]-sum[l-1])\ast x[l]$
[l,r] 区间都转移到r需要的花费

car(l,r)=(x[r]−x[l])∗(sum[r]−sum[l−1])−cal(l,r)$$car(l,r)=(x[r]-x[l])\ast (sum[r]-sum[l-1])-cal(l,r)$$

具体代码实现如下

const int maxn = 5e5+1000;
LL N,T;
LL x[maxn],a[maxn],sum[maxn],sumd[maxn];
//  sum[i] 表示到第i个点，共有多少product
//  sumd[i] 表示到第i个点，把这些点上所有的货物运送到0点需要的cost
//  把[l,r] 区间内的货物移到 l 则  ca1(l,r) = sumd[r]-sumd[l-1]-(sum[r]-sum[l-1])*d[l]
//  把[l,r] 区间内的货物移到 r 则  ca2(l,r) = (sum[r]-sum[l-1])*(x[r]-x[l])-ca1(l,r)
LL  ca2(LL l,LL r){
    return  sumd[r]-sumd[l-1]-(sum[r]-sum[l-1])*x[l];
}
LL  ca1(LL l,LL r){
    return  (sum[r]-sum[l-1])*(x[r]-x[l])-ca2(l,r);
} 
bool judge(LL mid){

    LL l ,r,i;
    LL mid2 = mid/2+1;
    // 假设l 为必选的位置，没有完全转移的箱子是 r
     l = 1,r = 1, i = 1;
    while(1){
        while( r <= N&& sum[r]-sum[l-1] < mid) r++;// 不足x就增加r
        while(i <= N&&sum[i]-sum[l-1] < mid2)  i++;// 求区间中位数所在的位置 
         if(r > N|| i > r) break;// 如果找不到符合条件的break出去 
        LL plus = sum[r]-sum[l-1]-mid;// 右端点可能会多plus个product 
        if((ca1(l,i)+ca2(i,r)-(x[r]-x[i])*plus )<= T) return true;
        l++;// 这一个左端点不行，换下一个
    }
    // 假设r 集装箱内所有物品都已经转移，而l可能没有转移完
     l = r = i = N;
    while(1){
        while(l >= 1&& sum[r]-sum[l-1] < mid) l--;
        while(i >= 2&& sum[r]-sum[i-1] < mid2) i--;
        if(i < l||l < 1)
           break;
        LL plus = sum[r]-sum[l-1]-mid;// 左端点可能多plus个product 
        if(ca1(l,i)+ca2(i,r)-(x[i]-x[l])*plus <= T) return true;
        r--;// 这个左端点不行，换下一个
    }
    return false;
}
int main(void)
{
    scanf("%lld %lld",&N,&T),T>>=1;
    for(int i = 1;i <= N; ++i)
      scanf("%lld",&x[i]);
    LL M = 0;
    for(int i = 1;i <= N; ++i)
       scanf("%lld",&a[i]),sum[i] = sum[i-1]+a[i],M = max(M,a[i]),sumd[i] = sumd[i-1]+a[i]*x[i];

    LL l = M,r = sum[N];

    while(l <= r){
      LL mid = l+(r-l)/2;
//      cout<<"mid = "<<mid <<" "<<judge(mid)<<endl;
      if(judge(mid))
         l = mid+1;
      else
         r = mid-1;
    }
    printf("%lld",r);
    return 0;
}