题意:给你一个字符串,只有.和,每次可以移动一次,使用最小的移动步数,使最终所有的‘*’集中在一起。
思路:贪心,都往中间靠,步数最小,首先将这些的下标存储起来,当的个数为偶数的时候,中间的数有俩,哪一个作为中位数都是可以的,可以手动推一下,这两个中位数之间的距离之不变的,你用哪个当中位数,都要走cnt/2-1个它,找到中位数之后,用每个的下标减去中位数坐标,再减去每个与最中间的相差几个,求出每一个相加的和,因为每移动一次,它后面的(中位数后面的*)或者前面的(中位数前面的)都会少走一步
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
string s;
int t,n;
int main(int argc, char** argv) {
scanf("%d",&t);
while(t--){
vector<int> v;
scanf("%d",&n);
getchar();
getline(cin,s);
for(int i=0;i<n;i++){
if(s[i]=='*'){
v.push_back(i);
}
}
int cnt=v.size();
long long sum;
for(int i=0;i<cnt;i++){
sum+=abs(v[i]-v[cnt/2])-abs(i-cnt/2);
}
printf("%lld\n",sum);
}
return 0;
}