首页 > 其他分享 >题解:CF1256D Binary String Minimizing

题解:CF1256D Binary String Minimizing

时间:2024-07-06 10:57:34浏览次数:19  
标签:int 题解 CF1256D 位置 交换 long ++ Minimizing 序列

贪心。

数据范围 \(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

相关文章

  • 2016 CSP-J/NOIP万字长文复赛真题题解——秒杀T1 买铅笔,T2 回文日期,T3 海港,T4 魔法
    [NOIP2016普及组]买铅笔题干[NOIP2016普及组]买铅笔题目背景NOIP2016普及组T1题目描述P老师需要去商店买nnn支铅笔作为小朋友们参加NOIP的礼物。她发现......
  • 端口占用问题解决方案(Windows)
    端口占用问题解决方案(Windows)在开发和运维过程中,我们经常会遇到端口被占用的情况。这可能导致服务器启动失败或者其他服务无法正常运行。本文将介绍如何使用命令行工具来查询和解决端口占用问题。一、查询当前所有端口使用情况可以使用netstat-ano命令来查看当前所有......
  • StarRocks数据导入慢问题解决
    一、问题描述依据StarRocks官网快速开始安装教程,用dockercompose安装了starrocks,log模块从rabbitMq的队列批量获取log消息,发现队列消息有堆积,一晚上下来大概能对接4000条消息。经单元测试发现insertinto到starrocks中时间竟然相差几百倍。mysql每条insertsql执行3.5mss......
  • 题解 - 定价
    题目题目描述你如此计算一个价格\(p\)(为正整数)的荒谬程度:首先将\(p\)看做一个由数字组成的字符串(不带前导\(0\));然后,如果\(p\)的最后一个字符是\(0\),就去掉它。重复这一过程,直到\(p\)的最后一个字符不是\(0\);记\(p\)的长度为\(a\),如果此时\(p\)的最后一位是......
  • 洛谷P5517题解
    题目解释现有一数列:\(a_{0}=-3,a_{1}=-6,a_{2}=-12,a_{n}=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n,求T组a_{n}\)modp的异或和题目思路分析抛开复杂度不谈,这道题可以用矩阵加速(矩阵的快速幂)和通项公式两种方法来做,这两种方法求一个\(a_{n}\)的时间复杂度都是\(log_2(n)\),但矩阵乘法需......
  • Kali网卡失效IP不显示问题解决
    因为我的个人习惯,通常为虚拟机配置两个网卡,一个Host-only网卡用于与主机进行通信、一个网络地址转换网卡用于访问网络。然而,在配置Kali主机时,常常遇到网络地址转换网卡断联的现象,导致虚拟机无法正常访问网络。根据先前的经验,问题出在网络配置上。查看/etc/network/interfaces文......
  • [题解]逃离地球
    题意简述有一个星系,共有\(n*m\)个星球,排成\(n\)行\(m\)列。初始星球之间没有道路。接下来给定\(P\)种魔法\(1\),\(Q\)种魔法\(2\):魔法\(1\):第\(i\)种魔法用\(a_i,b_i,c_i\)描述。表示你可以任选星系的一行,在第\(a_i\)和第\(b_i\)个星球之间建立一条航道,消耗\(c_i\)的能量。魔......
  • [题解]P1083 [NOIP2012 提高组] 借教室
    [题解]P1083[NOIP2012提高组]借教室解法\(1\):线段树-\(O((n+m)\logn)\)比较直观的一种做法,但是可能需要卡一下输入(这里没卡也过了,但要注意输入是\(10^6\)级的,为了保险一定要加)。#include<bits/stdc++.h>#definelc(x<<1)#definerc((x<<1)|1)#defineintlonglong......
  • SP15620 POSTERIN - Postering 题解
    题目传送门前置知识单调栈解法容易有每个建筑物的宽度对答案没有影响,故可以将其宽度均看作\(1\)。在最优策略下,对于每张海报,其高度一定等于所覆盖的楼的最小高度。单调栈维护最小高度,记录额外海报数量(与先前高度相等时可以少用一张海报)。最终,用总张数\(n\)减去额外海报......
  • reverse 题解
    reverse题解注意到本题数据范围较大且与数位有关,考虑数位DP。我们发现对于每个询问,我们可以将第一个条件拆开之后差分,可以先从后往前DP,预处理出末尾满足$L\le\operatorname{reverse}(n)\leR$的个数,之后使用试填法填数即可。具体地,在预处理时,处理出顶到上界,顶到下界......