C - Weird Sum-思维题

C - Weird Sum

题意：

给定n*m的矩阵 求相同的数的曼哈顿距离和

思路：

曼哈顿距离 ： dis_{i -> j}=|x_j - x_i| + |y_j - y_i| 可以发现x和y可以分开计算 我们先把多个x 和y升序排列 对于第i个x(y) 它需要被加i-1次被减n-i次 故就很好写代码了

#include  
#define ll long long
#define pi acos(-1)
#define F ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
ll  n, m, k;
vectorvx[N];
vectorvy[N];

int main()
{
    F; 
    cin >> n >> m;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll x; 
            cin >> x;
            vx[x].push_back(i);//把值为一样的点归为一个容器中 
            vy[x].push_back(j);        
        }
    }
    for(int i = 1; i <= 100001; i++){//每一类横纵坐标都升序排列 
        sort(vx[i].begin(), vx[i].end());
        sort(vy[i].begin(), vy[i].end());
    }
    for(int i = 1; i <= 100001; i++){
        for(int j = 0; j < vx[i].size(); j++){
            ans += j * vx[i][j];//对于第j（含0）个元素他要被加j次 
            ans -= (vx[i].size() - j - 1) * vx[i][j];//对于第j（含0）个元素他 要被减n-j-1次
            ans += j * vy[i][j];
            ans -= (vy[i].size() - j - 1) * vy[i][j];
        }
    }
        
    cout << ans << "\n";
    return 0;
}