题解 AT_abc380_c [ABC380C] Move Segment

题目大意

• 统计序列 $S$ 中，连续 $1$ 的部分有多少个。
• 将第 $k$ 个部分整体向前移，直到第 $k$ 个部分和第 $k-1$ 个部分合并成为一个部分是，输出此时的序列 $S$。

数组定义

• $id$ 数组：用于记录第 $i$ 个部分的起始坐标。
• $shu$ 数组：用于记录第 $i$ 个部分的元素个数。

思路

第一部分—处理 连续 $1$ 的部分

• 如果 $S[i]=1$，就让 $number+1$；
• 如果 $S[i]=0$，并且 $s[i-1]=1$。代表这是一个新的部分，进行 $cnt+1$ ，此时将第 $cnt$ 个部分的 $id$ 值赋为 $last$，第 $cnt$ 个部分的 $shu$ 值记为 $number$，并将 $number$ 清 $0$。
• 如果 $S[i]=0$，并且 $s[i+1]=1$。代表即将有一个新的部分，则需要将 $last$ 赋值为下一个部分的起始坐标。

第二部分—移动 第 $k$ 个部分

• 我们既然已将统计了每个部分的起始坐标，不妨将第 $k$ 个部分的起始坐标 直接给瞬移到 第 $k-1$ 个部分的终点坐标的下一位，就可以解决顺义问题啦！
• 但有个问题，如何去算终点坐标呢？我们在知道第 $i$ 个部分的起始坐标和数量后，利用 $start+len-1$ 的计算公式，就可以轻松求解了。

第三部分—输出序列 $S$

• 我们利用计算终点坐标的公式可以算出第 $i$ 个区间的终点坐标，然后判断当前坐标是否在这个区间里。如果在输出 $1$，否则输出 $0$。
• 如果当前坐标的下一个坐标为下一个区间的起始坐标，则更新 $last$ 的值。

代码部分

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
string s;
int id[1000010];
int shu[1000010];
int cnt;
signed main()
{
	cin>>n>>k;
	cin>>s;
	int number=0,last=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='1')
		{
			number++;
		}
		else if(s[i-1]=='1'&&s[i]=='0')
		{
			id[++cnt]=last;
			shu[cnt]=number;
			number=0;
		}
		if(s[i]=='0'&&s[i+1]=='1')
		{
			last=i+1;
		}
	}
	if(number!=0)
	{
		id[++cnt]=last;
		shu[cnt]=number;
		number=0;
	}
	id[k]=id[k-1]+shu[k-1];
	int now=1;
	for(int i=0;i<n;i++)
	{
		if(i>=id[now]&&i<=id[now]+shu[now]-1)
		{
			cout<<1;
		}
		else
		{
			cout<<0;
		}
		if(i+1==id[now+1])
		{
			now++;
		}
	}
	return 0;
}