中位数定理

https://codeforces.com/contest/2149/problem/D

点击查看代码

#include <bits/stdc++.h>
#define int long long
using namespace std;int f(const vector<int> x){if(x.empty())return 0;int pos = (int)x.size() / 2;int ans = 0;for(int i = 0; i < x.size(); i ++){ans += abs(abs(pos - i) - abs(x[pos] - x[i]));//cout << ans << endl;}return ans;
}void solve(){int n;string s;cin >> n >> s;//cout << s << endl;vector<int> a;vector<int> b;for(int i = 0; i < n; i ++){if(s[i] == 'a')a.push_back(i);else b.push_back(i);}cout << min(f(a),f(b)) << endl;
}signed main(){int t;cin >> t;while(t --){solve();}return 0;
}

每个a或者到b的坐标,往中间靠是最小代价