P2512 [HAOI2008] 糖果传递

北斗七星 · 2025-11-20 09:20:11 · 个人记录

P2512 [HAOI2008] 糖果传递

方法一：

费用流，过不了

方法二：

不难发现，传递路线不会交叉，所以如果题目不是环，是序列的情况下，可以直接 O(n) 贪心解决

考虑破环，枚举 1 号点和 n 号点传递的量，即可变成序列的情况

显然会超时，不难发现是单峰函数，三分即可，时间复杂度为 O(n\log n)

代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+50,inf=2e9;
int n,a[N],b[N],ans=1e18,to;
int work(int x){
    int tot=abs(x);
    for(int i=1;i<=n;i++) b[i]=a[i];
    b[n]+=x; b[1]-=x;
    for(int i=1;i<n;i++){
        if(b[i]<to) tot+=to-b[i],b[i+1]-=to-b[i];
        else tot+=b[i]-to,b[i+1]+=b[i]-to;
    }
    return tot;
}
main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),to+=a[i];
    to/=n;
    int L=-inf,R=inf;
    while(L+3<=R){
        int x=L+(R-L)/3,y=L+(R-L)*2/3;
        if(work(x)<work(y)) R=y-1; 
        else L=x;
    }
    for(int i=L;i<=R;i++) ans=min(ans,work(i));
    printf("%lld\n",ans);
}

方法三：

设 x_i 为 i-1 号点传递给 i 号点的个数， x_1 为 n 给 1 的

那么有 a_i+x_i-x_{i+1}=to ，即 x_{i+1}=(a_i-to)+x_i

设 c_i=a_i-to ，则 x_i=x_1+\sum_{j=1}^{i-1}c_j

答案为 \sum_{i=1}^n |x_i| ，排序后让 x_1 取中位数即可

代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+50;
int n,a[N],to,c[N],ans;
main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),to+=a[i];
    to/=n;
    for(int i=2;i<=n;i++) c[i]=c[i-1]+a[i-1]-to;
    sort(c+1,c+n+1);
    int x=-c[(n+1)/2];
    for(int i=1;i<=n;i++) ans+=abs(x+c[i]);
    printf("%lld\n",ans);
}