贪心。
数据范围 \(n \le 10^{6}\),因此我们要用时间复杂度为 \(\mathcal{O}\left( n \right)\) 的算法来解决这个问题。
思路
从左至右扫一遍序列,如果遇到 \(10\) ,则要将这个 \(0\) 交换到前面的位置。由于是字典序最小,\(0\) 应该尽量在最高位。现在需要知道这个 \(0\) 被交换到哪个位置,因此我们有变量 \(t\) 来记录下一个 \(0\) 所在的位置。
记刚才找到的 \(10\) 的 \(0\) 的位置为 \(i\)。则要交换 \(i-t\) 次,我们只需要判断 \(k\ge i-t\) 是否成立即可。
如果成立,则直接交换,将 序列的第 \(t\) 个位置置为 \(0\),第 \(i\) 个位置,置为 \(1\)。这样成立的原因是因为序列的第 \(t\) 到 \(i-1\) 这些位置的数不可能有 \(0\),因此我们并不需要去移动,直接 \(\mathcal{O}\left( 1 \right)\) 交换即可。
如果不成立,则尽量向前交换,将序列的第 \(i-k\) 个为位置置为 \(0\)(还能交换 \(k\) 次),第 \(i\) 个位置置为 \(1\),这样做的正确性与上文相同。
代码
注意小特判:如果序列的前面一段都是 \(0\) 则 \(t\) 的初始值应为这一段的最后一个位置 \(+1\)。
开 long long
否则爆炸,\(n^{2}\ge 2147483647\)。\(2147483647\) 为 int
最大值。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,t;
const int maxn=1e6+5;
int a[maxn];
void Main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
char ch;
cin>>ch;
a[i]=ch-'0';
}
int t=1,g=1;
while(a[g]==0) t++,g++;
for(int i=2;i<=n;i++){
if(a[i-1]==1&&a[i]==0){
if(k>=i-t){
k-=i-t;
a[t]=0,a[i]=1;
if(k==0) break;
t++;
}
else{
a[i-k]=0,a[i]=1;
break;
}
}
}
for(int i=1;i<=n;i++) cout<<a[i];
cout<<"\n";
}
signed main(){
int T;
cin>>T;
while(T--) Main();
return 0;
}
标签:int,题解,CF1256D,位置,交换,long,++,Minimizing,序列
From: https://www.cnblogs.com/sapo1o/p/18286997