题解：P9982 [USACO23DEC] Haybale Distribution G

题目大意

数轴上有

N

个定点，你需要取一个点，使得这个点到其左边的定点的距离的和的

a

倍加上这个点到其右边的定点的距离的和的

b

倍最小。

思路分析

简单数学题。

假设我们现在第

p

定点到第

p+1

个定点之间，往右移动一个单位对答案造成的影响就是

ap-b(n-p)

而这个值是答案在整数域上的“微分”，因此，当它从负变成正时，答案可以取到最值。

令

ap-b(n-p)\le0

ap-bn+bp\le0

(a+b)p\le bn

因为

a>0

，

b>0

，所以

a+b>0

。则

p\le\frac{bn}{a+b}

因为从第

p

个定点到第

p+1

个定点的过程中，变化依旧是负的，所以我们将

y

设在第

p+1

个定点上，就有最小值。

计算答案则用前缀和优化一下即可。
时间复杂度

O(q+n\log n)

。

Talk is cheap,show me the code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
int n,q,x[N],sum[N][2];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i];
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++)sum[i][0]=sum[i-1][0]+x[n]-x[i]+1;
    for(int i=n;i>=1;i--)sum[i][1]=sum[i+1][1]+x[i]-x[1]+1;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        int p=b*n/(a+b)+1;
        cout<<(sum[p][0]-p*(x[n]-x[p]+1))*a+(sum[p][1]-(n-p+1)*(x[p]-x[1]+1))*b<<'\n';
    }

    return 0;
}

题解：P9982 [USACO23DEC] Haybale Distribution G

文章操作

题目大意

思路分析

Talk is cheap,show me the code

相关推荐

评论

题解：P9982 [USACO23DEC] Haybale Distribution G