首页 > 编程语言 >挑战程序设计竞赛 2.2章习题 POJ - 3617 Best Cow Line 贪心

挑战程序设计竞赛 2.2章习题 POJ - 3617 Best Cow Line 贪心

时间:2024-05-18 11:08:34浏览次数:23  
标签:顺序 Cow 3617 队列 首字母 注册 习题 奶牛 FJ

FJ正准备带着他的N头奶牛(1 ≤ N ≤ 2,000)参加一年一度的“年度最佳农民”比赛。在这个比赛中,每个农民都会将他的奶牛排成一行,然后引导它们经过评委。

今年比赛的组织者采用了一种新的注册方案:只需按照它们出现的顺序注册每头奶牛的首字母(即如果FJ带着Bessie、Sylvia和Dora依次出场,他只需注册BSD)。
注册阶段结束后,每个小组将按照奶牛名字首字母的字符串按递增的字典顺序进行评判。

FJ今年非常忙,必须赶回农场,所以他希望尽快接受评判。他决定在注册之前重新排列已经排好队的奶牛。

FJ标记了一个新的竞争奶牛排队位置。然后,他开始将奶牛从旧队列中依次发送到新队列的末尾,每次可以选择发送原队列中的第一头或最后一头奶牛(剩余的)到新队列的末尾。
完成后,FJ按照这个新顺序带着他的奶牛进行注册。

给定他的奶牛的初始顺序,确定他可以通过这种方式制作的最小字典顺序字符串。

输入
* 第1行:一个整数:N
* 第2行到第N+1行:第i+1行包含原始队列中第i头奶牛的单个首字母('A'..'Z')

输出
他可以制作的最小字典顺序字符串。每行(最后一行除外)包含新队列中的80头奶牛的首字母('A'..'Z')。

6
A
C
D
B
C
B


ABCBCD

贪心解法
主要注意左右两边优先选择字典序优先的字母 如果两段字母相同 那么就考虑下一层的字母

标签:顺序,Cow,3617,队列,首字母,注册,习题,奶牛,FJ
From: https://www.cnblogs.com/itdef/p/18199140

相关文章

  • P4183 [USACO18JAN] Cow at Large P
    题目首先有结论:一个点为关键点(可以由该点的子树中出发,正好在该点拦截住奶牛),当且仅当\(g_u\ledist(root,u),g_{fa}>dist(root,fa)\),其中\(g_u\)表示距离\(u\)最近的叶节点。那么\(18pts\)就是\(O(n^2)\)的暴力了voiddfs(intu,intfa){ dis[u]=(G.d[u]==......
  • 使用qemu-system-x86_64和cloud-init修改qcow2镜像密码
    方法来自于:CoretutorialwithQEMU依次执行下面的命令sudoaptinstallqemu-system-x86mkdirtempcdtemp#以此镜像为例wgethttps://cloud-images.ubuntu.com/jammy/current/jammy-server-cloudimg-amd64.imgcat<<EOF>user-data#cloud-configpassword:123ch......
  • shell脚本习题
    目录1.计算1到100所有整数的和2.提示用户输入一个小于100的整数,并计算从1到该数之间所有整数的和3.求从1到100所有整数的偶数和、奇数和4.用户名存放在users.txt文件中,每行一个,判断文件里的用户是否存在,若该用户存在,输出提示该用户已存在;用户存在但没设密吗,则提示用户并让用户设置......
  • P2340 [USACO03FALL] Cow Exhibition G
    原题链接题解1.考虑到每个牛只有选或不选两种选择,这样暴力搜索的思路便产生了2.还是上面的思路,怎么优化呢?想想背包数组,其下标是什么?是体积其值是是什么?是价值是在体积相同的情况下选择价值最高的,本题也是,最优解一定是相同智商里情商最高的3.价值和体积都是负数,怎么解决?cod......
  • LCD屏显示图片习题【一】
    目录LCD屏显示图片习题题目解析代码完整展示LCD屏显示图片习题题目解析​ 该题的显著要求有两个,一是任意位置,二是任意大小。为满足这两个要求得先读取并记录bmp数据,且bmp文件属于普通文件,所以选择标准IO函数fopen()打开bmp,并用结构体变量进行记录;然后为了提升用户使用体验,即b......
  • P2853 [USACO06DEC] Cow Picnic S
    简单的一道深搜:思路:让每个有奶牛的农场沿着道路跑下去,跑到的农场加上root地方的奶牛数量,最后统计能有k头奶牛的农场数量就是答案代码:#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#inclu......
  • The cowherd and the weaving maid
    ThecowherdandtheweavingmaidInthecelestialcourtoftheJadeEmperorlivedsevenprincesses.Eachhadtheirchosenplaceincourt,buttheyoungestprincesshadaspecialskill.Shecouldpluckcloudsfromtheskyandspinthemintothesoftestrob......
  • Python-有序字典OrderedDict练习题
    问题:读取键盘输入结果,创建n个键值对,将其排序后放入有序字典并输出。详细描述:根据提示,实现函数功能:读取n(n>0)行输入,以每一行的数据为key,行号(从0开始)为value,建立n对键值对,然后将他们按照key排序后,放入一个有序字典,最后输出这个有序字典。importcollectionsdefFunc():pairs......
  • python 基础习题 for循环
    1.用for循环打印出从1到10的所有整数,输出如下:12345678910  2.  声明如下变量:aString='Python'..........#请补齐以上省略号处的for循环语句,使得输出结果是:当前字母:P当前字母:y当前字母:t当前字母:h当前字母:o当前字母:n 最好用两种方法,一个使用不......
  • 标准IO练习题
    目录标准IO练习题题目:分析:代码展示结果展示总结知识扩展time()函数localtime()函数标准IO练习题题目:设计程序,获取当前系统时间,把时间转换为特定格式”yy年mm月dd日星期xtt:mm:ss”,并每隔1s写入到本地磁盘中一个叫做log.txt的文本中,如果文本不存在则创建。分析:本题目需要利......