专栏文章

题解：AT_abc421_c [ABC421C] Alternated

zzet365
AT_abc421_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minz1niv
此快照首次捕获于
2025/12/02 10:41
3 个月前
此快照最后确认于
2025/12/02 10:41
3 个月前
查看原文

题目: [ABC421C]Alternated

题目链接：https://www.luogu.com.cn/problem/AT_abc421_c

题目翻译:

给你一个长度为2n的字符串，里面有A,B若干个，对这个字符串进行任意次数的相邻字符交换，求字符串中不存在相同字符相邻的情况所需的最少操作次数。
这道题很简单，我们先考虑考虑，答案无非就两种， 一种是ABABABAB... 一种事ABABABA... 然后我们分开讨论一下就可以写出代码啦！
CPP
#include <bits/stdc++.h>
using namespace std;

int n,c1,c2;
string s;
int a[510000],b[510000];
long long k1 = 0,k2 = 0;

int main()
{
    cin >> n >> s;
    for(int i = 0;i < 2 * n;i++)
	{
        if(s[i] == 'A') a[c1++] = i;
        else b[c2++] = i;
    }
    for(int i = 0;i < n;i++) k1 += abs(a[i] - 2 * i); //ABABABAB...
    for(int i = 0;i < n;i++) k2 += abs(b[i] - 2 * i); //BABABABA...
    cout << min(k1,k2);
}
这是我的第一篇题解，希望管理大大能通过~

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...