题目大意
小c是一名oier。最近，他发现他的数据结构好像学傻了。因为他在刷题时碰到了一道傻逼数据结构题，强行使用了平衡树来解决，卡着时间AC。为此，他被狠狠地嘲讽了一番。于是，小c找了大量的数据结构题来做。
昨天，小c正在吃寿司，突然发现许多盘寿司围成了一个圆圈，这些寿司中有红色的也有蓝色的。由于小c看交错的颜色非常不爽，想通过一些操作，使得所有的红色寿司形成了一块连续的区域，蓝色的寿司也形成了一块连续的区域。如果小c每次只可以交换相邻的两盘寿司，那么最少需要多少步才可以达到小c的要求呢？由于他做题做多了，脑袋已经有点不清醒了，于是这个问题就交给你了。
题目分析
这题考试暴力写错成功爆零。
观察题目，发现移动R和移动B是等效的，因此随便选择一个移动。
假设移动R，不难发现其实这是一个带权中位数的问题，尽量地将其他的R移动到最中间的R是最优的做法。
故将环扩展$2$倍展开成为序列，长度为$2len$。枚举中间点，预处理出其左边的$\lceil\frac{len}{2}\rceil$个移动到当前点的代价以及右边的$\lfloor\frac{len}{2}\rfloor$个移动到当前点的代价。
然后使用$O(n)$的时间枚举中间点即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=2000005;
LL t,Left[maxn],Right[maxn],ans;
int main() {
t=Get_Int();
while(t--) {
char s[maxn];
scanf("%s",s+1);
int n=strlen(s+1);
LL t1=ceil((double)n/2),t2=n/2,tot=0;
ans=1e18;
for(int i=1; i<=n; i++) {
s[n+i]=s[i];
tot+=(s[i]=='R');
}
n*=2;
LL sum=0,cnt=0;
for(int i=1; i<=n; i++) {
if(i-t1>=1&&s[i-t1]=='R') {
sum-=(t1-cnt);
cnt--;
}
if(s[i]=='R')cnt++;
else sum+=cnt;
Left[i]=sum;
}
sum=0,cnt=0;
for(int i=n; i>=1; i--) {
if(i+t2<=n&&s[i+t2]=='R') {
sum-=(t2-cnt);
cnt--;
}
if(s[i]=='R')cnt++;
else sum+=cnt;
Right[i]=sum;
}
for(int i=t1+1; i<=n-t2; i++)ans=min(ans,Left[i]+Right[i+1]);
printf("%lld\n",ans);
}
return 0;
}
|
