【算法】字典序最小的 01 字符串

ops/2024/9/23 9:30:37/

字典序最小的 01 字符串

题目描述

小红有一个 01 字符串,她可以进行最多 k 次提作,每次操作可以交换相邻的两个字符,问可以得到的字典序最小的字符串是什么。

输入描述

第一行包含两个整数,n(1 < n < 10^5)和 k(1 < k < 10^9),表示字符串的长度和可以进行的操作次数。

接下来一行一个长度为 n 的 01 字符串。

输出描述

输出一个长度为 n 的字符串,表示字典序最小的字符串。

输入示例
5 2
01010
输出示例
00101
思路:

贪心,模拟

每次只能交换相邻的两个字符,从前向后遍历字符,如果遇到10组合的要交换,同时k–,注意交换后的情况是前面有可能会出现10组合,因此k>0时要回退,直到(用while)前面没有10组合或k==0为止

10101//1,2交换,回退检查前面没有出现10
01101//3,4交换
01011//回退检查发现10组合,1,2交换
#include<bits/stdc++.h>
using namespace std;
int main()
{int a,b;cin>>a>>b;string s;cin>>s;for(int i=0;i<a;i++){int j=i;while(i!=0&&s[i-1]=='1'&&s[i]=='0'){swap(s[i],s[i-1]);b--;i--;if(b==0){cout<<s<<endl;return 0;}}i=j;}cout<<s;return 0;
}

http://www.ppmy.cn/ops/86629.html

相关文章

《数据结构1800题》基础回合总结——第1章 绪论

前言&#xff1a;《数据结构1800》这本书相信大家或多或少都有所耳闻&#xff0c;收录了诸多不同档次学校的考研真题&#xff0c;因为和汤老师的1800撞名所以备受调侃。这1800道题目里面有选择有填空&#xff0c;也有简答和一些编程题&#xff0c;总的来说质量良莠不齐——亦或…

MATLAB基础:函数与函数控制语句

今天我们继续学习Matlab中函数相关知识。 API的查询和调用 help 命令是最基本的查询方法&#xff0c;可查询所有目录、指定目录、命令、函数。 我们直接点击帮助菜单即可查询所需的API函数。 lookfor 关键字用于搜索相关的命令和函数。 如&#xff0c;我们输入lookfor inpu…

MATLAB R2017a 安装与破解 ​编辑

转载自 https://www.cnblogs.com/chaofn/p/8323852.html 第一步&#xff1a; 到我的百度网盘下载MatlAB2017a的原安装程序和破解补丁&#xff1a; 链接&#xff1a;百度网盘 请输入提取码 提取密码&#xff1a; d59m 第二步&#xff1a; 下载的两个iso文件&#xff1a;R2…

DHCP笔记

DHCP---动态主机配置协议 作用&#xff1a;为终端动态提供IP地址&#xff0c;子网掩码&#xff0c;网关&#xff0c;DNS网址等信息 具体流程 报文抓包 在DHCP服务器分配iP地址之间会进行广播发送arp报文&#xff0c;接收IP地址的设备也会发送&#xff0c;防止其他设备已经使用…

《数据结构与算法之美》学习笔记三之链表

前言&#xff1a;先回顾一下本系列上一篇文章的大致内容 二叉树 1、二叉树的分类&#xff1a;满二叉树(所有节点都是满满的)、完全二叉树(只有最后一层不满&#xff0c;且最后一层节点都在左边)、二叉搜索树(有顺序)、平衡二叉树(左右子树高度差不超过1或者一棵空树) 2、二叉树…

“八股文”:程序员的福音还是梦魇?

——一场关于面试题的“代码战争” 在程序员的世界里&#xff0c;“八股文”这个词儿可谓是“如雷贯耳”。不&#xff0c;咱们可不是说古代科举考试中的那种八股文&#xff0c;而是指程序员面试中的那些固定套路的题目。如今&#xff0c;各大中小企业在招聘程序员时&#xff0…

137.只出现一次的数字Ⅱ

1.题目描述 给你一个整数数组 nums &#xff0c;除某个元素仅出现 一次 外&#xff0c;其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 示例 1&#xff1a; 输入&#xff1a;nums …

Linux服务器单个大文件上传内存限制修改

/etc/apache2/apache2.conf 添加: <Directory /var/www/html> LimitRequestBody 0 </Directory> /etc/php/7.4/apache2/php.ini 修改: upload_max_filesize 1000G post_max_size 1000G max_execution_time 0 max_input_time 0 memory_limit -1 验证修…