【sorting】CF861div2 B. Playing in a Casino

分手后的思念是犯贱 2024-03-22 11:47 15阅读 0赞

[Problem - B - Codeforces][]

题意：

![bc69405d97954b0fadec5ee22997bc76.png][]

![9b0bed012cad44b49e7b84bb6b7da5b3.png][]

思路：

枚举超时-->只枚举一个指针，然后直接算贡献

注意到列与列之间的贡献互不影响，因此可以考虑对于每一列都去sort一遍，然后只枚举一个指针，直接算贡献

**直接想贡献想不清楚的时候，要不列式子，要不手推样例**

![165259912d8345be8f8b77f939381a94.png][]

对每一列都sort，可以开一个vector存一下

**题中n\*m<=3e5也暗示我们开vector，因为数组不知道要开多大**

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    
    vector<int> a[mxn];
    
    int N,M,x;
    
    int work(vector<int> &b){
    	int res=0,sum=0;
    	for(int i=0;i<b.size();i++){
    		res+=b[i]*i-sum;
    		sum+=b[i];
    	}
    	return res;
    }
    void solve(){
    	cin>>N>>M;
    	for(int j=1;j<=M;j++) a[j].clear();
    	for(int i=1;i<=N;i++){
    		for(int j=1;j<=M;j++){
    			cin>>x;
    			a[j].push_back(x);
    		}
    	}
    	int ans=0;
    	for(int j=1;j<=M;j++){
    		sort(a[j].begin(),a[j].end());
    		ans+=work(a[j]);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - B - Codeforces]: https://codeforces.com/contest/1808/problem/B
[bc69405d97954b0fadec5ee22997bc76.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/ad66073f44324ba9becd7d25c99805e2.png
[9b0bed012cad44b49e7b84bb6b7da5b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b8a21ef736104fc2b2e0c0b2530e78af.png
[165259912d8345be8f8b77f939381a94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f863f51b50d348509e3b82c13cbcdc8c.png