HZOJ 寿司

这题也是挺神仙的，现在O(n)的解法还没打出来，只是用O(nlogn)卡过去了（理论上可以过），sdfz某大佬用三分拿到了65分……

考试连暴力都没打出来……

n²暴力T40：

首先将环拆成链，我们可以O（n）枚举一个点不动，将它左右的点向他靠近，总复杂度O($n^2$).

代码也挺简单，貌似我的代码比别人都短……可能思路有点不一样。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #define LL long long
 6 #define MAXN 2000010
 7 #define max(a,b) ((a)>(b)?(a):(b))
 8 #define min(a,b) ((a)<(b)?(a):(b))
 9 #define ma(x) memset(x,0,sizeof(x))
10 using namespace std;
11 char a[MAXN];
12 int n,T;
13 signed main()
14 {
15     cin>>T;
16     while(T--)
17     {
18         n=0;char te=getchar();
19         while(te!='B'&&te!='R')te=getchar();
20         while(te=='B'||te=='R'){a[++n]=te;te=getchar();}
21         for(int i=n+1;i<2*n;i++)a[i]=a[i-n];
22         LL ans=0x7fffffff;
23         for(int i=1;i<=n;i++)
24         {
25             LL sum=0,nb=0,nr=0;
26             for(int j=i+n-1;j>=i+n-n/2;j--)
27                 if(a[j]==a[i])sum+=i+n-j-nb-1,nb++;
28             for(int j=i+1;j<=i+n/2;j++)
29                 if(a[j]==a[i])sum+=j-i-1-nr,nr++;
30             if(n%2==0&&a[i+n/2]==a[i])sum+=min(n/2-nb-1,n/2-nr-1);
31             ans=min(ans,sum);
32         }
33         cout<<ans<<endl;
34     }
35 }

View Code

nlogn二分：

对于一段序列，一定有一个分界点，将它左边的红色移到左端，右边的红色移到右端使得答案最优，而此时左右另一种颜色各占一半（我觉得有点难以理解），所以这个分界点可以二分查找，加上枚举序列起点总复杂度nlogn。

另外还有一个难点就是O（1）求步数。

预处理出i点左右红色数量rl，rr，蓝色数量bl，br，将i左端红色全不移动到最左端所需步数sl，最右端sr。

可以O(n)扫一边处理出来。

在枚举得到mid之后，就可一O（1）求出当前序列最优答案：

ans=sl[mid]-sl[l-1]-(rl[mid]-rl[l-1])*bl[l-1] + sr[mid+1]-sr[r+1]-(rr[mid+1]-rr[r+1])*br[r+1];

说一下左半部分，右半部分是类似的，sl[mid]-sl[l-1]是将[l,r]中所有红色移到序列最左端所需步数，而我们只需要将其移到枚举的端点的左端，所以要减去后边的东西。

如果把sl[mid]-sl[l-1]按递推式子拆开那么就很好理解了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #define LL long long
 6 #define MAXN 2000010
 7 #define max(a,b) ((a)>(b)?(a):(b))
 8 #define min(a,b) ((a)<(b)?(a):(b))
 9 #define ma(x) memset(x,0,sizeof(x))
10 using namespace std;
11 char a[MAXN];
12 int n,T;
13 LL sl[MAXN],sr[MAXN],rl[MAXN],rr[MAXN],bl[MAXN],br[MAXN];
14 LL solve(int l,int r)
15 {
16     int L=l,R=r,mid,end=(rl[r]-rl[l-1])>>1;
17     while(L<=R)
18     {
19         mid=(L+R)>>1;
20         if(rl[mid]-rl[l-1]==end)break;
21         if(rl[mid]-rl[l-1]>end) R=mid-1;
22         if(rl[mid]-rl[l-1]<end) L=mid+1;
23     }
24     LL ans=sl[mid]-sl[l-1]-(rl[mid]-rl[l-1])*bl[l-1]+sr[mid+1]-sr[r+1]-(rr[mid+1]-rr[r+1])*br[r+1];
25     return sl[mid]-sl[l-1]-(rl[mid]-rl[l-1])*bl[l-1]+
26            sr[mid+1]-sr[r+1]-(rr[mid+1]-rr[r+1])*br[r+1];
27 }
28 signed main()
29 {
30     cin>>T;
31     while(T--)
32     {
33         n=0;char te=getchar();
34         while(te!='B'&&te!='R')te=getchar();
35         while(te=='B'||te=='R'){a[++n]=te;te=getchar();}
36         for(int i=n+1;i<=2*n;i++)a[i]=a[i-n];
37         LL ans=0x7ffffffffffffff;
38         
39         rl[0]=bl[0]=sl[0]=0;
40         for(int i=1;i<=n*2;i++)
41         {
42             rl[i]=rl[i-1],bl[i]=bl[i-1];
43             sl[i]=sl[i-1];
44             if(a[i]=='B')bl[i]++;
45             else rl[i]++,sl[i]+=bl[i];
46         } 
47         rr[n*2+1]=br[n*2+1]=sr[n*2+1]=0;
48         for(int i=n*2;i>=1;i--)
49         {
50             rr[i]=rr[i+1],br[i]=br[i+1];
51             sr[i]=sr[i+1];
52             if(a[i]=='B')br[i]++;
53             else sr[i]+=br[i],rr[i]++;
54         }
55         for(int i=1;i<=n;i++)
56             ans=min(ans,solve(i,i+n-1));
57         cout<<ans<<endl;
58     }
59 }

View Code

O（n）正解：

用两个单调指针既可实现O（n），代码先留个坑。