题解：[ABC380C] Move Segment

sjh0626 · 2024-11-16 22:44:58 · 题解

所有的题不一定需要华丽的代码，但一定需要你认真的思考，如这道题。

题意概括

指定一个长度为 N 的字符串，其中只包含 0 与 1，并且指定一个整数 K，让你把第 K-1 个 1 分块移动到 K 分块的后面。

• 1 分块指任意一个 i 代表的 S_i 都为 1，我们定义字符串的开头下标为 l，结尾下标为 r，则 l \le i \le r。

思路分析

我们需要把第 K-1 个 1 分块移动到 K 分块的后面，则先需要把每一个分块给划分出来。

即把每一个分块（0 分块和 1 分块）存到一个字符串数组 a 里面。

再把每一个 1 分块的下标存到一个整数数组 b 里面。

我们只需将 a 的第 b_k 个元素和 a 的第 b_k-1 个元素交换即可。

如样例一：

分块存进 a 数组后。

把 1 分块存进数组 b。

将 a 的第 b_k 个元素和 a 的第 b_k-1 个元素交换。

工作完成，输出。

代码解析

#include<bits/stdc++.h>
#define sjh0626s return
#define code 0
using namespace std;
int n,k,si,pos[600010],pi;
string s,arr[600010]; 
void split(string s){ //分块 
    string temp;
    s=s+"2"; //防止处理不到最后一个分块 
    for(int i=0;i<s.size()-1;i++){
        temp+=s[i];
        if(s[i]!=s[i+1]){
            arr[++si]=temp;
            if(arr[si][0]=='1')pos[++pi]=si;
            temp="";
        }
    }
}
int main(){
    cin>>n>>k>>s;
    split(s);
    swap(arr[pos[k]],arr[pos[k]-1]); //交换分块 
    for(int i=1;i<=si;i++){
        cout<<arr[i];
    }
    sjh0626s code; //完结撒花！ 
}