Codeforces Round #719 (Div. 3)E. Arranging The Sheep

给一个字符串, *代表羊, .代表空位, 求怎么移动能让羊排成一列.

这题是acwing的那个模板题的衍生, 要先找到中间羊, 然后找到它的位置, 然后平移(坐标 – 第几个), 求和即可.

#include "bits/stdc++.h"
using namespace std;   
// fast read
const auto fr = [](){
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(12);
    return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main() { 
    fr; 
    int T;
	cin >> T;
	while (T--)
	{ 
		int N;
		cin >> N;
		string s;
		cin >> s;
		ll res = 0;
		ll count = 0;
		for (int i = 0; i < N; i++)
		{
			if(s[i] == '*')
			{
				count++;
			}
		}
		if(count == 0 || count == N)
		{
			cout << 0 << endl;
			continue;
		}
		ll t = -1;
		ll med = -1;
		for (int i = 0; i < N; i++)
		{
			if(s[i] == '*')
			{
				t++;
			}
			if(t == count / 2)
			{
				med = i;
				break;
			}
		}
		ll tt = med - count / 2;
		for (int i = 0; i < N; i++)
		{
			if(s[i] == '*')
			{
				res += abs(tt - i);
				tt++;
			}
		}
		cout << res << endl;
	}
	
    return 0; 
}