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

算法设计与分析算法实现——删数问题

通过棋盘输入一个高精度的正整数n(n的有效位数<=240)去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。变成对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。
输入:n,s
输出:最后剩下的最小数
输入实例:
178543
4
输出示例:
13

首先题目的意思是,在不改变数字原有位置的前提下,删除s个数,使得剩下的数按照原有位置构成的新数字值最小。
那么数组不可进行排序来改变原有序列,易知,想要最后获得的数最小,那么越高位的数(数组下标越小的数)值要越小。
因此从前向后遍历数组,选择一定范围里最小的数,作为最后新数的高位,同时又要使得后面的数位够用。
这个一定的范围就是滑动窗口,滑动窗口的始端可以设置为构成新数上一个高位在原数组的位置的下一个;滑动窗口的末端必须不超过原数组的长度,又要保持原数组后面的位数构成新数够用。
因此两层循环,外层循环控制窗口不会超出原数组;内层循环求窗口内的最值。

在这里插入图片描述

//解题思路
//易知,越高位的数越小,则最后得数越小
//顺着数组从前向后滑动窗口,求窗口内的最小值
#include<iostream>
#include<cstdio> 
#include<string> 
using

http://www.kler.cn/news/136649.html

相关文章:

  • 基于NVIDIA NIM平台—生成属于自己的DIY食谱
  • 随机抽取学号
  • c语言内核链表
  • Windows 11优化利器:全方位定制你的操作系统
  • GS-SLAM Dense Visual SLAM with 3D Gaussian Splatt 论文阅读
  • PDF.js的使用及其跨域问题解决
  • Node.js环境配置级安装vue-cli脚手架
  • Java面试题07
  • 一文了解:离散型制造业轻量化MES解决方案
  • SD3403/SS928 烧录 Uboot Kernel Rootfs是什么
  • WiFi 6的数据在发送端分片和在接收端重组的理解
  • 【快应用】快应用学习之兄弟组件通信
  • Vue框架学习笔记——创建Vue实例、实例与容器对应关系
  • C语言的5个内存段你了解吗?( 代码段/数据段/栈/堆)
  • Python将原始数据集和标注文件进行数据增强(随机仿射变换),并生成随机仿射变换的数据集和标注文件
  • 【C++ Primer Plus学习记录】for循环
  • 51.Sentinel微服务保护
  • 架构探索之路-第一站-clickhouse | 京东云技术团队
  • C++设计模式——单例模式
  • 基于单片机GPS轨迹定位和里程统计系统
  • 全国见!飞桨星河社区五周年,邀你共赴大模型盛宴!
  • 什么是调试和性能分析工具?
  • 【广州华锐互动】VR虚拟现实技术助力太空探险:穿越时空,探索宇宙奥秘
  • 第二证券:龙头公司大手笔回购 港股今年以来回购总额逼近千亿港元
  • 基于Java封装继承多态实现的一个简单图书系统
  • 【论文阅读】MAG:一种用于航天器遥测数据中有效异常检测的新方法