链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1543
类型:贪心
原题:
Company Macrohard has released it’s new version of editor Nottoobad, which can understand a few voice commands. Unfortunately, there are only two voice commands that it can understand – “repeat the last word”, “delete the last symbol”. However, when one
uses “repeat the last word” the editor inserts a blank that separates the words. But the company claims that it is possible to type much faster – simply by less number of presses. For example, such a phrase like “this thin thing” requires only 6 presses of
the keyboard.
Action
|
Number
of presses
|
Content of the document
|
Press "this"
|
4
|
This
|
Say “repeat the last word”
|
0
|
thisthis
|
Say “delete the last symbol”
|
0
|
this thi
|
Press "n"
|
1
|
thisthin
|
Say “repeat the last word”
|
0
|
this thin thin
|
Press "g"
|
1
|
this thin thing
|
In order to increase the popularity of it’s product the company decided to organize a contest where the winner will be a person who types a given number of words with minimum number of presses. Moreover, the first word must be typed first, and all the others
can be typed in arbitrary order. So, if words “apple”, “plum” and “apricote” must be typed, the word “apple” must be typed first, and the words “plum” and “apricote” can be switched. And the most important for you – you are going to take part in the contest
and you have a good friend in the company, who told you the word which will be used in the contest. You want be a winnerJ, so you have to write a program which finds the order of the words, where the number of presses will be minimum.
Input
The first line of the input contains the T (1≤T≤15) the number of test cases. Then T test cases follow. The first line of each test contains a number N (1≤N≤100) – the number of words that must be pressed. Next N lines contain words – sequences of small
Latin letters, not longer than 100 symbols. Remember that the first word must be pressed first!
Output
The first line of the output contains number X - the minimum number of presses, which one has to do in order to type all the words using editorNottoobad. Next N lines contain the words in that minimum order. If there are several solutions, you
can output one of them.
样例输入:
3
3
this
thin
thing
4
popcorn
apple
apricote
plum
2
hello
hello
样例输出;
6
this
thin
thing
21
popcorn
plum
apricote
apple
5
hello
hello
分析与总结:
贪心题,每次直接遍历选择一个可以减少输入次数最少的单词即可。
代码:
/*
* UVa: 10602 - Editor Nottoobad
* Result: Accept
* Time: 0.020s
* Author: D_Double
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#define MAXN 120
using namespace std;
struct Node{
int no;
char word[110];
friend bool operator < (const Node &a, const Node &b){
return a.no < b.no;
}
}arr[MAXN];
int main(){
int T, N;
char str[110];
scanf("%d", &T);
while(T--){
scanf("%d",&N);
for(int i=0; i<N; ++i){
scanf("%s",arr[i].word);
arr[i].no = -1;
}
arr[0].no = 1;
int ans=strlen(arr[0].word);
int rank=1, last=0;
while(rank < N){
int t=-1, cnt=0;
for(int i=0; i<N; ++i)if(arr[i].no==-1){
if(t==-1){
t=i;
if(arr[i].word[0]==arr[last].word[0]){
for(int j=0; j<strlen(arr[i].word)&&j<strlen(arr[last].word); ++j){
if(arr[i].word[j]!=arr[last].word[j]) break;
else ++cnt;
}
}
}
else{
int tmp=0;
for(int j=0; j<strlen(arr[i].word)&&j<strlen(arr[last].word); ++j){
if(arr[i].word[j]!=arr[last].word[j]) break;
else ++tmp;
}
if(tmp > cnt){
t=i; cnt=tmp;
}
}
}
ans += (strlen(arr[t].word) - cnt);
arr[t].no = rank++;
last = t;
}
sort(arr, arr+N);
printf("%d\n", ans);
for(int i=0; i<N; ++i)
puts(arr[i].word);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
毕业设计物流管理系统的设计与实现(Java版本) 采用Struts2+hibernate+Oracle10g+Tomcat 涉及车辆管理,配送点管理,运输方式管理,订单管理,员工管理,用户管理,部门管理,权限管理,角色管理等基础管理功能。
基于VB+access实现的成绩分析统计系统(论文+源代码) 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
ASP+ACCESS网上购物系统设计(源代码+设计说明书+调研报告).zip
污水处理计算书
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
ASP+ACCESS在线考试系统设计(源代码+设计说明书).zip
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip 毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip 毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip毕业设计基于知识图谱和循环神经网络的推荐系统python源码+数据集.zip
行业报告
基于matlab实现的导线网平差,主要是附和导线平差程序,用于计算各点坐标并评定其精度。.rar
基于VB+access实现的学生学籍管理系统(系统+论文) 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。
ASP基于BS的工艺品展示系统的设计与实现(源代码+设计说明书).zip
污水处理计算书
ASP+ACCESS网上花店毕业设计全套(设计说明书+源代码+说明).zip
污水处理计算书
行业报告
ASP基于WEB教学评估系统设计(源代码+设计说明书).zip
JSP教师档案管理系统(源代码+设计说明书).zip