【思維-數列-字典序-貪心】CF-Div3-Round 598——D Binary String Minimizing

前言

一波三折，還好在最後幾分鐘AC了，超激動qwq...

題目

time limit per test：1 second

memory limit per test：256 megabytes

input：standard input

output：standard output

You are given a binary string of length nn (i. e. a string consisting of nn characters '0' and '1').

In one move you can swap two adjacent characters of the string. What is the lexicographically minimum possible string you can obtain from the given one if you can perform no more than kk moves? It is possible that you do not perform any moves at all.

Note that you can swap the same pair of adjacent characters with indices ii and i+1i+1 arbitrary (possibly, zero) number of times. Each such swap is considered a separate move.

You have to answer qq independent test cases.

Input

The first line of the input contains one integer qq (1≤q≤1041≤q≤104) — the number of test cases.

The first line of the test case contains two integers nn and kk (1≤n≤106,1≤k≤n21≤n≤106,1≤k≤n2) — the length of the string and the number of moves you can perform.

The second line of the test case contains one string consisting of nn characters '0' and '1'.

It is guaranteed that the sum of nn over all test cases does not exceed 106106 (∑n≤106∑n≤106).

Output

For each test case, print the answer on it: the lexicographically minimum possible string of length nn you can obtain from the given one if you can perform no more than kk moves.

Example

input

3
8 5
11011010
7 9
1111100
7 11
1111100
      

output

01011110
0101111
0011111
      

Note

In the first example, you can change the string as follows: 

In the third example, there are enough operations to make the string sorted.

題目大意

給你一個長度為n的01串，可以最做k次操作，每次操作把任意兩個相鄰的數交換

求字典序最小的操作後（可以不進行操作）的01串

分析

因為要求字典序最小且原數列隻包含0和1，是以要盡可能地把0往前移

一來就想到暴力：

找到每個0，如果前一個數是1,、還能進行操作（k>=1）并且0還能往前移（不在位置1上），就一直交換

但是沒想第二個點就TLE.../太不給面子了QAQ！

認識到暴力交換不行，就考慮換個更優的算法：算出每個0能到達的位置

首先如果不考慮k的限制，那麼每個0肯定是盡可能往前移，直到遇到0停下

0就在最前面“堆起來了”：100011101——>000011111

如果加上k的限制，其實變化不大，隻是要看“ k能把目前的0盡可能往前移到哪個位置 ”，兩種情況：

設 f 為目前0的位置，last 為目前0的前面一個0的位置 

1.k >= f - last - 1（k大于等于0能往前移的最多步數）

2.k< f - last - 1

标記有0的位置（ans[ i ]=1），最後輸出時判斷該位置是0還是1即可qwq~

一番TLE後，又WA了，原來是k沒開long long ，離比賽結束隻有幾分鐘，終于A了，緊張死我了

做題要點總結

1.本題多組資料，初始化不能用memset，不然會逾時得很慘...

2.好好看資料範圍！記得開long long ！原題目範圍：

3.多組資料，輸出記得換行

TLE代碼

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6;
int a[MAXN+5],id[MAXN+5];
int n,k,cnt;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		//memset(id,0,sizeof(id));
		cnt=0;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%1d",&a[i]);
			if(a[i]==0)
				id[++cnt]=i;
		}
		for(int i=1;i<=cnt;i++)
		{
			int f=id[i];
			while(k>=1&&f>1)//還能操作 
			{
				if(a[f-1])
				{
					swap(a[f-1],a[f]);
					k--,f--;
				}
				else
					break;
			} 
		}
		for(int i=1;i<=n;i++)
			printf("%d",a[i]);
		printf("\n");
	}
	return 0;
}
           

AC代碼

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6;
ll a[MAXN+5],id[MAXN+5],ans[MAXN+5];
ll n,k,tot;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		tot=0;
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%1d",&a[i]);
			if(a[i]==0)
			{
				id[++tot]=i;
				ans[i]=1;//順便把ans初始化，memset要逾時 
			}
			else
				ans[i]=0;
		}
		if(!tot||tot==n)//簡單判斷特殊情況 
		{
			for(int i=1;i<=n;i++)
				if(ans[i])
					printf("0");
				else
					printf("1");
			printf("\n");
			continue;
		}
		ll last=0;//記錄目前0前面一個0的位置 
		for(int i=1;i<=tot;i++)
		{
			ll f=id[i];
			if(k>=f-last-1)//能移到前一個0的後面一位 
			{
				k-=(f-last-1);
				last++;
				ans[f]=0,ans[last]=1;//原位置不再是0，新位置是0 
			}
			else//k<f-last-1
			{
				ans[f]=0,ans[f-k]=1;//往前最多能移k位 
				break;
			}
		}
		for(int i=1;i<=n;i++)
			if(ans[i])
				printf("0");
			else
				printf("1");
		printf("\n");
	}
	return 0;
}
           

總結

這道題在比賽時做了有點久，主要是一開始沒意識到memset會逾時

不過最終還是在比賽結束前AC了，開心