当前位置: 首页 > news >正文

N. Number Reduction

Problem - 1765N - Codeforces

image-20231004212521844

发现如果是无前导0最小数那么在保证删除k个数时第1位是最小的,第二位一定是相对最小的,且答案第一位和第二位在原位置的间隔是小于等于还可以删除的位数的。

因此,对于原数字长度位n,要删除k,那么答案长度为n - k,这n - k位每一个都是优先选小的,如果不能再选较大值(对于首位比较特殊,不能出现前导零,因此首位从1开始),可以从第1位开始进行枚举0到9将n - k位进行填充。

每一次选完后,这一个数前面可能还有没有选的,但是由于已经选过该位,再选前面的会导致答案变大,因此不要。

可以用10个队列存入每一个数的下标,用一个变量last记录上一个在原数字中选择的数的下标。对每一位依次遍历0到9这10个队列,如果当前数字队列满足条件:

  • 这个数字的下标大于等于上一个下标+1
  • 这个数字的下标跟上一个下标之间差值小于等于还可以删除的次数

满足这些条件时表示下一位是该数字,之后将这个last和还能删除的位进行更新,退出循环到下一位进行判断即可。

代码:

void solve() {string s; cin>>s;int k; cin>>k;int n = s.size();queue<int> q[10];for(int i = 0; i < n; ++i) q[s[i] - '0'].push(i);string ans = "";int last = 0, len = n - k;for(int i = 0; i < len; ++i) {for(int j = (i == 0); j < 10; ++j) {// 如果数字下标小于等于上一个下标,进行出队(因为以后都用不上了,大于上一位的下标才是可能有用的while(q[j].size() && q[j].front() < last) q[j].pop();// 如果满足当前位和上一位之间差值是小于等于还可以删除的数次数,表示可以if(q[j].size() && q[j].front() - last <= k) {ans += j + '0';k -= q[j].front() - last;last = q[j].front() + 1;break;}}}cout<<ans<<endl;
}

CF1765N Number Reduction - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

相关文章:

N. Number Reduction

Problem - 1765N - Codeforces 发现如果是无前导0最小数那么在保证删除k个数时第1位是最小的&#xff0c;第二位一定是相对最小的&#xff0c;且答案第一位和第二位在原位置的间隔是小于等于还可以删除的位数的。 因此&#xff0c;对于原数字长度位n&#xff0c;要删除k&#…...

Java集合面试题

一、Java集合面试题 1.LinkedHashMap底层原理&#xff1f; HashMap是无序的&#xff0c;迭代HashMap所得到元素的顺序并不是它们最初放到HashMap的顺序&#xff0c;即不能保持它们的插入顺序。 LinkedHashMap继承于HashMap&#xff0c;是HashMap和LinkedList的融合体&#x…...

Python 编程基础 | 第三章-数据类型 | 3.5、列表

一、列表 1、创建列表 序列是Python中最基本的数据结构&#xff0c;Python有6个序列的内置类型&#xff0c;但最常见的是列表和元组。序列都可以进行的操作包括索引&#xff0c;切片&#xff0c;加&#xff0c;乘&#xff0c;检查成员。此外&#xff0c;Python已经内置确定序列…...

Spring Cloud Zuul 基本原理

Spring Cloud Zuul 底层是基于Servlet实现的&#xff0c;核心是通过一系列的ZuulFilter来完成请求的转发。 1、核心组件注册 1.1. EnableZuulProxy注解 启用Zuul作为微服务网关&#xff0c;需要在Application应用类加上EnableZuulProxy注解&#xff0c;而该注解核心是利用Im…...

QT实现TCP服务器客户端的实现

ser&#xff1a; widget.cpp&#xff1a; #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//实例化一个服务器server new QTcpServer(this);// 此时&#xf…...

行为型设计模式——责任链模式

摘要 责任链模式(Chain of responsibility pattern): 通过责任链模式, 你可以为某个请求创建一个对象链. 每个对象依序检查此请求并对其进行处理或者将它传给链中的下一个对象。 一、责任链模式意图 职责链模式&#xff08;Chain Of Responsibility&#xff09; 是一种行为设…...

window安装压缩版postgresql

环境&#xff1a; window 11 专业版postgresql-16.0-1-windows-x64-binaries.zip 一、下载 1.1 从官网下载 https://www.postgresql.org/download/windows/ 1.2 从百度网盘下载 链接&#xff1a;https://pan.baidu.com/s/1fmQbgWSzX4hN07Lgdzfz0g?pwddzyy 提取码&#…...

数组(数据结构)

优质博文&#xff1a;IT-BLOG-CN 一、简介 数组Array是一种线性表数据结构&#xff0c;它用一组连续的内存空间&#xff0c;存储一组具有相同类型的数据。 数组因具有连续的内存空间的特点&#xff0c;数据拥有非常高效率的“随机访问”&#xff0c;时间复杂度为O(1)。但因要保…...

C/C++ 二分查找面试算法题

1.二分查找&#xff08;有序数组&#xff09; https://blog.csdn.net/qq_63918780/article/details/122527681 1 #include <stdio.h>2 #include <string.h>3 4 int func(int *a,int j,int x)5 {6 int len j - 1,i 0,min;7 while(i<len)8 {9 …...

Linux基本指令(上)——“Linux”

各位CSDN的uu们好呀&#xff0c;今天&#xff0c;小雅兰的内容是Linux啦&#xff01;&#xff01;&#xff01;主要是Linux的一些基本指令和Linux相关的基本概念&#xff08;系统层面&#xff09;&#xff0c;下面&#xff0c;让我们进入Linux的世界吧&#xff01;&#xff01;…...

XSS详解

XSS一些学习记录 XXS短标签、属性、事件、方法短标签属性事件函数弹窗函数一些对于绕过有用的函数一些函数使用payload收集 浏览器编码问题XML实体编码URL编码JS编码混合编码 一些绕过方法利用constructor原型污染链构造弹框空格绕过圆括号过滤绕过其他的一些绕过 参考 XXS短标…...

【图论】判环问题

&#xff08;未更新完、做到相关题再更新相关部分 文章目录 无向图判断有无环并输出环上点 无向图判断有无环并输出环上点 例题&#xff1a;H. Mad City 利用变种拓扑排序&#xff0c;先把度为1的点存入队中&#xff0c;每次取出队头&#xff0c;遍历邻接点&#xff0c;再将该…...

将3D MAX设计模型导入NX1988

将3D MAX设计模型导入NX1988 概述导入流程导出喜欢的模型对模型进行修改模型贴图 概述 一般家装设计都不会用NX之类的产品设计软件&#xff0c;也没有通用的文件格式可以互相转换&#xff0c;本文的目的是将从网上下载的一些设计较好的3D MAX模型导入到NX软件中借用&#xff0…...

操作系统原理实验三:页面调度算法程序

实验三&#xff1a;页面调度算法程序 课程名称&#xff1a;操作系统原理 项目名称&#xff1a;页面调度算法程序 实验&#xff08;实训&#xff09;类型&#xff1a;验证性实验 实验&#xff08;实训&#xff09;课时&#xff1a;2 [目的和要求] 目的&#xff1a; 加深对请…...

QT实现tcp服务器客户端

服务器.cpp #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//实例化一个服务器server new QTcpServer(this);// 此时&#xff0c;服务器已经成功进入监听状态…...

tcp拥塞控制原理

18.3 拥塞控制 我们在向对端发送数据时&#xff0c;并不是一股脑子任意发送&#xff0c;因为TCP建立连接后&#xff0c;就是建立了一根管道&#xff0c;这跟管道上&#xff0c;实际上有很多的工作设备&#xff0c;比如路由器和交换机等等&#xff0c;他们都会对接收到的TCP包进…...

【C++设计模式之简单工厂模式】分析及示例

简介 简单工厂模式是一种常见的设计模式&#xff0c;用于创建多种相似对象的实例&#xff0c;属于创建型。 它通过一个工厂类来解耦客户端代码和对象的创建过程&#xff0c;使得客户端无需直接和具体的产品类交互&#xff0c;而只需要通过工厂类获取所需的产品实例即可。 原理…...

云原生定义整理

云原生定义整理 Pivotal 是云原生应用的提出者&#xff0c;并推出了 Pivotal Cloud Foundry 云原生应用平台和 Spring 开源 Java 开发框架&#xff0c;成为云原生应用架构中先驱者和探路者。 Pivotal最初的定义 Pivotal公司的Matt Stine在2015年写了一本叫做<<迁移到云…...

华硕X555YI, Win11下无法调节屏幕亮度

翻出一个旧电脑华硕X555YI&#xff0c;装Win11玩&#xff0c;已经估计到会有一些问题。 果然&#xff0c;装完之后&#xff0c;发现屏幕无法调节亮度。试了网上的一些方法&#xff0c;比如修改注册表等&#xff0c;无效。 估计是显卡比较老&#xff0c;哪里没兼容。然后用驱动…...

踩坑 | vue动态绑定img标签src属性的一系列报错

文章目录 踩坑 | vue项目运行后使用require()图片也不显示问题描述vue中动态设置img的src不生效问题的原因require is not defined 解决办法1&#xff1a;src属性直接传入地址解决办法2 踩坑 | vue项目运行后使用require()图片也不显示 问题描述 在网上查阅之后&#xff0c;发…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...