【枚举+sorting+递推（DS思想）】 ABC186 D - Sum of difference

浅浅的花香味﹌ 2024-03-22 18:16 12阅读 0赞

一发过！

有点CF的感觉

[D - Sum of difference (atcoder.jp)][D - Sum of difference _atcoder.jp]

题意：

![6440a483226246acb60f55a6e33c5fc3.png][]

思路：

O(n^2)超时，肯定是O(n)算

因为算的是所有对的贡献，因此数列是无序的

因此可以把数列排个序

然后注意到相邻两个数的贡献是可以递推的，比较相邻两个数的贡献即可

![f51bb4bef5d84c9ca08dbd25d7f98552.jpeg][]

![218ffff47577420cbbb9b1a9eff27596.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N;
    int a[mxn],F[mxn];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++) cin>>a[i];
        sort(a+1,a+1+N);
        for(int i=2;i<=N;i++) F[1]+=a[i]-a[1];
        for(int i=2;i<=N;i++){
            F[i]=F[i-1]-a[i]-a[i]*(N-i)+a[i-1]*(N-(i-1));
        }
        //for(int i=1;i<=N;i++) cout<<F[i]<<" \n"[i==N];
        int ans=0;
        for(int i=1;i<=N;i++) ans+=F[i];
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Sum of difference _atcoder.jp]: https://atcoder.jp/contests/abc186/tasks/abc186_d
[6440a483226246acb60f55a6e33c5fc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5138d7622a444b34924fe3cffc80b18f.png
[f51bb4bef5d84c9ca08dbd25d7f98552.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/c1c644473a1d4e7a8887c1e22d47c26c.png
[218ffff47577420cbbb9b1a9eff27596.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/565723a380fb4e308214a147f7061a4a.png