打卡信奥刷题（3051）用C++实现信奥题 P6709 [CCC 2020] Swapping Seats

张开发
• 2026/4/19 20:42:46 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（3051）用C++实现信奥题 P6709 [CCC 2020] Swapping Seats
P6709 [CCC 2020] Swapping Seats题目描述有N NN个人坐在一张圆桌旁。共有三个派别每一个人属于一个派别。现在您想使属于同一派别的人坐到一起。您可以每次将两个人交换位置输出最小的交换次数。输入格式仅一行一个长度为N NN的字符串s ss为顺时针所有人的派别。如果s i s_isi​为A则说明第i ii个人为第一个派别的以此类推。输出格式仅一行一个整数表示最小的交换次数。输入输出样例 #1输入 #1BABCBCACCA输出 #12说明/提示样例解释BABCBCACCA → AABCBCBCCA → AABBBCCCCA \texttt{BABCBCACCA}\to\texttt{AABCBCBCCA}\to\texttt{AABBBCCCCA}BABCBCACCA→AABCBCBCCA→AABBBCCCCA。子任务本题采用捆绑测试且本题的 Subtask 分数有微调。Subtask 126 2626分s i ∈ { s_i\in\{si​∈{A, ,,B} \}}且N ≤ 5 × 10 3 N\le 5\times 10^3N≤5×103。Subtask 227 2727分s i ∈ { s_i\in\{si​∈{A, ,,B} \}}。Subtask 327 2727分N ≤ 5 × 10 3 N\le 5\times 10^3N≤5×103。Subtask 420 2020分无特殊限制。对于100 % 100\%100%的数据保证s i ∈ { s_i\in\{si​∈{A, ,,B, ,,C} \}}1 ≤ N ≤ 10 6 1\le N\le 10^61≤N≤106。说明本题译自 Canadian Computing Competition 2020 Senior T4 Swapping Seats。C实现#includebits/stdc.husingnamespacestd;constintmaxn2000002;intn,sa[maxn],sb[maxn],sc[maxn],suma,sumb,sumc,ansINT_MAX;chara[maxn];intmo(intx){returnx%(n1)1;}signedmain(){scanf(%s,a1);nstrlen(a1);for(intin1;i(n1);i)a[i]a[i-n];for(inti1;in;i)if(a[i]A)suma;elseif(a[i]B)sumb;elsesumc;for(inti1;i(n1);i){sa[i]sa[i-1](bool)(a[i]A);sb[i]sb[i-1](bool)(a[i]B);sc[i]sc[i-1](bool)(a[i]C);}for(inti1;in;i){// positions for A beginsintnx1isuma,nx2;// B is nextnx2nx1sumb;ansmin(ans,max(sb[nx1-1]-sb[i-1],sa[nx2-1]-sa[nx1-1])sumc-sc[in-1]sc[nx2-1]);// C is nextnx2nx1sumc;ansmin(ans,max(sc[nx1-1]-sc[i-1],sa[nx2-1]-sa[nx1-1])sumb-sb[in-1]sb[nx2-1]);}returncoutansendl,0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章