首页 > 编程语言 >213. 字典序最小问题 Best Cow Line(挑战程序设计竞赛)

213. 字典序最小问题 Best Cow Line(挑战程序设计竞赛)

时间:2023-01-02 12:33:28浏览次数:66  
标签:字符 213 NN 输出 Cow 尾部 Line 字典

地址 https://www.papamelon.com/problem/213

给定一个字符 SS,长度为 NN。由 SS 构成出新的字符串 TT,长度也为 NN。

起初 TT 是一个空串,然后执行 NN 次操作,每次操作有两种选择:

从 S 头部删除一个字符,加到 T 的尾部
从 S 尾部删除一个字符,加到 T 的尾部
我们要决定一种最优的操作方案,使得 T 串的字典序最小。

输入
第一行整数 N(1≤N≤2000),表示 S 串的长度
接下来 N 行,每行一个大写英文字符,表示 S 串的每个字符
输出
输出一行或多行:每行最多 80 个字符,当 T 串太长,需要换行再继续输出
样例 1
输入
6
A
C
D
B
C
B
输出
ABCBCD

解答
贪心算法
从字符串S中左右两端取出字典序较小的那个 放入T中 比如 s= acdb 那么最后 t=abcd
需要考虑的特殊情况就是 两边都相同的情况下 s= abccccba,那么需要左右双指针同时向中间移动监测,直到某一边出现了字典序较小的结果,或者两端相遇 那就随机选择

我的视频题解空间

标签:字符,213,NN,输出,Cow,尾部,Line,字典
From: https://www.cnblogs.com/itdef/p/17019727.html

相关文章

  • 机器学习技法---(Week1)Linear Support Vector Machine
      技法的课,相对更关注算法,希望1个月内搞掂~课程介绍  共计16周课程,主要内容:哲学上直观的理解、关键理论、核心算法和实际操作的注意点。围绕特征变换,本次课程涉及到以......
  • 通过Gitlab管理Jenkins Pipeline流水线
    1、首先需要将已经调试好的Jenkinspipeline文件上传到git库中,推荐以Jenkinsfile命名放至git库根目录gitadd.gitcommit-m"pipelinev1"gitpush-uoriginmain......
  • Jenkins Pipeline快速入门
    目录一、Pipeline安装二、语法讲解一、Pipeline安装Pipeline,简单来说,就是一套运行在Jenkins上的工作流框架,将原来独立运行于单个或多个节点的任务连接起来,实现单个任务难......
  • [USACO22DEC] Cow College B 题解
    洛谷P8897AcWing4821题目描述有\(n\)头奶牛,每头奶牛愿意交的最大学费位\(c_i\),问如何设置学费,可以使赚到的钱最多。\(1\len\le10^5,1\lec_i\le10^6\)做法分析......
  • IfcOwnerHistory
    IfcOwnerHistory实体定义IfcOwnerHistory定义所有历史和标识相关信息。为了提供快速访问,它直接连接到所有独立的对象、关系和属性。 IfcOwnerHistory用于标识创建和拥......
  • TigerTail-Pulsar Candidate Sifting and Synthesis Pipeline
    说明:2022年12月31日,在此记录自己的脉冲星候选体筛选、候选体折叠的脚本。需要安装必要的python包,Presto,ImageMagick(convert),基本的python,shell语言知识才能......
  • Centos7上使用jenkins执行pipeline在容器内部拉取环境运行代码的各种坑
    环境Centos7上部署了三个服务bitbucket192.168.1.156:7900jenkins192.168.1.156:8080docker服务原理在Dockerfile中定义pipelinescripts,然后拉取dockerhub的镜像作......
  • QLineSeries和 QBarSeries的用法
    #include<QtWidgets/QApplication>#include<QtWidgets/QMainWindow>#include<QtCharts/QChartView>#include<QtCharts/QBarSeries>#include<QtCharts/QBarSet>#include......
  • [oeasy]python0036_牛说_cowsay_小动物说话_asciiart_figlet_lolcat_管道(祝大家新年
    ​ 牛说(cowsay)回忆上次内容上次我们研究了shell脚本的编程并且在shell中实现了循环语句延迟命令清屏命令python命令figlet命令​编辑还能整点什么......
  • [ABC221D] Online games
    [ABC221D]Onlinegames难度:\(832\)标签:差分离散化\(\mathtt{blog}\)有\(n\)个区间\([a_i,a_i+b_i)\),问各被\(1\simn\)个区间覆盖的数字个数有多少个。\(n\le......