翻译:
你正在玩“安排羊”游戏。这个游戏的目标是让羊排好队。游戏中的关卡是由长度为𝑛的字符串描述的,由角色的’组成。'(空格)和'*'(绵羊)。在一个动作中,你可以移动任何羊向左或向右移动一个方格,如果相应的方格存在并且为空的话。一旦羊群排好队,游戏就结束了,也就是说,羊群之间不应该有空格子。
例如,如果𝑛=6,并且关卡由字符串“**.*..”描述,那么就可能出现以下游戏场景:
4位的羊向右移动,水平状态:“**..*.”;
2位的羊向右移动,水平状态:“*.*.*.”;
位置1的羊向右移动,水平状态为:“.**.*.”;
3位的羊向右移动,水平状态:“。*.**.”;
位置2的羊向右移动,水平状态:“..***.”;
羊排好队,比赛结束。
对于一个特定的关卡,你需要确定完成该关卡所需的最小移动数。
输入
第一行包含一个整数𝑡(1≤𝑡≤104)。然后是𝑡测试用例。
每个测试用例的第一行包含一个整数𝑛(1≤𝑛≤106)。
每个测试用例的第二行包含一个长度为𝑛的字符串,由字符'组成。’(空白)和‘*’(绵羊)——关卡的描述。
可以保证在所有测试用例中𝑛的总和不超过106。
输出
对于每个测试用例,输出完成关卡所需的最小移动数。
例子
inputCopy
5
6
* * . * . .
5
*****
3.
*。
3.
...
10
*.*...*.**
outputCopy
1
0
0
0
9
思路:
要把羊移动到一起,所以我们可以设一个方向,集体往哪边移动,最左和最右,中间都会有多余不必要的操作,而且两端的移动次数叠加都是最大的,所以我们选中心点,然后来让两边移动。
代码:
#include <iostream>#include <algorithm>#include <string.h>#include <string>#include <math.h>#include <stdio.h>#include<vector>#include<queue>#include<map>#include<set>#include<tuple>#include<numeric>#include<stack>using namespace::std;typedef long long ll;int n,t;inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');}string s;void solv(){cin>>n>>s;vector<int>q;int bj=0;for (int i =0; i<s.size(); i++) {if (i!=0&&s[i]!=s[i-1]) {bj=1;}if (s[i]=='*') {q.push_back(i);}}if (!bj) {printf("0\n");return;}int zz=(q.size())/2;zz=q[zz];ll ans=0;int ff=0,se=0;int l=zz-1,r=zz+1;while (l>=0) {if (s[l]=='*') {ans+=zz-l-1-ff;ff++;}l--;// printf("%lld\n",ans);}while (r<s.size()) {if (s[r]=='*') {ans+=r-zz-1-se;se++;}r++;// printf("%lld\n",ans);}printf("%lld\n",ans);}int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {solv();}return 0;}