将星号聚拢到中间的那个星号上,可以使得总路程最短。每个星号的路程花费是其距离中间星号之间的点号个数。最开始自己想到的方法是前缀和维护,但是TLE了。
前缀和维护(会TLE)
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #define LL long long 6 using namespace std; 7 const int N=1000050; 8 char w[N]; 9 int star[N]; //记录星号的位置 10 int n; 11 LL s[N]; //记录点号的前缀和 12 int main(){ 13 14 15 int T; 16 cin>>T; 17 while(T--){ 18 scanf("%d",&n); 19 memset(s,0,sizeof(s)); 20 scanf("%s",w+1); 21 int cnt=0; 22 for(int i=1;i<=n;i++){ 23 if(w[i]==‘*‘) star[++cnt]=i; 24 else s[i]++; 25 s[i]+=s[i-1]; 26 } 27 LL res=0; 28 int mid=cnt/2+1; 29 int p=star[mid]; //中间星号的位置 30 for(int i=1;i<mid;i++){ //对于左边的 31 res+=s[p]-s[star[i]-1]; 32 } 33 for(int i=mid+1;i<=cnt;i++){ 34 res+=s[star[i]]-s[p-1]; 35 } 36 printf("%lld\n",res); 37 } 38 39 40 41 return 0; 42 43 }
正解如下:
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #define LL long long 6 using namespace std; 7 const int N=1000050; 8 char w[N]; 9 int star[N]; //记录星号的位置 10 int n; 11 int main(){ 12 13 14 int T; 15 cin>>T; 16 while(T--){ 17 scanf("%d",&n); 18 scanf("%s",w+1); 19 int cnt=0; 20 for(int i=1;i<=n;i++){ 21 if(w[i]==‘*‘) star[++cnt]=i; 22 } 23 LL res=0; 24 int mid=cnt/2+1; 25 int p=star[mid]; //中间星号的位置 26 for(int i=1;i<mid;i++){ //对于左边的 27 res+=(p-star[i]-1)-(mid-i-1); //当前星号和中间星号之间相差的位数,减去这之间的星号数,就是这之间的点号数 28 } 29 for(int i=mid+1;i<=cnt;i++){ 30 res+=(star[i]-p-1)-(i-mid-1); 31 } 32 printf("%lld\n",res); 33 } 34 35 36 37 return 0; 38 39 }
Codeforces Round #719 (Div. 3) E. Arranging The Sheep
原文:https://www.cnblogs.com/talk-sea/p/14749484.html