1 solutions

  • 0
    @ 2024-10-25 16:59:25

    对于每个人和平均值ave相比,要么少要么多,此时引用一个x[i]表示i人和i - 1之间的交易,正负可表示传递方向,得出公式: a[i] + x[i] + x[i + 1] = ave (其中x[i]有正有负)后面将设定大于0,表示当前i人向左传递数量

    A1-X1+X2=ave -> X2=ave-A1+X1 = X1-C1 (假设C1=A1-ave)这里引入一个c
    A2-X2+X3=ave -> X3=ave-A2+X2=2ave-A1-A2+X1=X1-C2 (即C2=A1+A2-2ave=A2+C1-ave)
    我们希望Xi的绝对值之和尽量小,即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小
    所以找一个x1满足这个条件。
    

    ac code:

    #include<bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    const int N = 1e6 + 10;
    int n;
    LL a[N],su,ave,ans;
    LL c[N];
    int main ()
    {
    	cin >> n;
    	for(int i = 1;i <= n;++ i)
    	{
    		cin >> a[i];
    		su += a[i];
    	}
    	ave = su / n;
    	for(int i = 1;i <= n;++ i)
    	{
    		c[i] = c[i - 1] + ave - a[i - 1];
    	}
    	sort(c + 1,c + 1 + n);
    	LL m = c[(n + 1) / 2];
    	for(int i = 1;i <= n;++ i)
    	{
    		ans += abs(m - c[i]);
    	}
    	cout << ans;
    	return 0;
    }
    
    • 1

    Information

    ID
    7002
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    30
    Accepted
    3
    Uploaded By