正经题解｜Drogon

题意解析

给出一个字符串，长度为$n$，字符只有.与*。可以选择一次操作将$*$移动到左边或者右边的.当中。求解最少多少次才可以将*拼在一起。

算法解析

• 根据题目意思可以得知，最终目的是将$*$拼在一起，那么如何才能以最少步数拼在一起呢，首先我们得需要有一个集合点 。集合点很明显不可以以最远两个端点的中心点作为答案，因为这样会导致中心的火球移动的次数变多，所以最贪心方法是以最中心的火球去作为集合点。
• 假如我们要以中心的火球去作为中心点，那么我们就可以选择将左右部分的火球作为需要移动计算的板块。同时每移动一个火球到中心的左/右侧，那么剩余未到的火球他们的移动距离都会减少1格。也就是说，中心点$pos$会随着移动的次数不停的$+/-$ $ 1$。
• 那么我们由此可以发现一件事，其实当中心点固定后，那么其实就已经固定了总体移动次数，无论你移动的顺序是近先还是远先。
• 并且因为中心点的贪心最优决策成立，那么问题就由原本的确定最少移动次数 转变为求解其他顶点到达中心点侧步数的问题了。

时间复杂度

只需要计算每个火球到达中心点的欧氏距离，时间复杂度$O(n)$

STD标程

#include<bits/stdc++.h>
using namespace std;


int main(){
	int n;
	cin >> n ;
	string s;
	cin >> s;
	int cnt = 0 ;// 代表一共有几个火球 
	for(int i = 0 ; i < n ; i ++ )
	{
		cnt += (s[i] == '*' ? 1 : 0);
	}
	int pos = -1 ; // 中心点
	int cur = -1; // 半场火球数 
	
	for(int i = 0 ; i < n ; i ++ )
	{
		if(s[i] == '*'){
			cur ++ ; // 计算半场火球 
			if(cur == cnt / 2){ 
				pos = i; // 记录中心点火球的坐标
			}
		}
	}
	long long answer = 0 ;
	cur = pos - cnt / 2; 
	for(int i = 0 ; i < n ; i ++ )
	{
		if(s[i] == '*'){
			answer += abs(cur - i ); // 求解累加距离 
			cur ++ ; 
		}
	}
	cout << answer << endl;	
	return 0;
}