首页 > 其他 > 详细

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

时间:2021-05-10 09:11:39      阅读:20      评论:0      收藏:0      [点我收藏+]

一、算法分析

将星号聚拢到中间的那个星号上,可以使得总路程最短。每个星号的路程花费是其距离中间星号之间的点号个数。最开始自己想到的方法是前缀和维护,但是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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!