uva 10152 ShellSort

时间:2022-04-13 12:56:34

//这个算法用到了“相对位置”的思想,并且就本题而言还有一个很重要的结论就是,假设

//移动了k个元素,那么这k个元素一定是最后结果的那个序列的前k个元素,而且易知,

//越先移动的元素一定会越被压在移动的元素的底部

首先找到需要移动的字符串,方法如下:以初始序列为准,设初始序列下标为i, 目的序列下标为j, 从n-1开始,如果两下标对应的字符串相等,下标同时减一,否则仅初始序列下标减一。那么目的序列中还未被成功匹配的字符串就是需要移动的字符串。要使移动次数最少,显然应该按未被处理的目的序列中字符串逆序移动(输出)。

uva 10152 ShellSort

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=210;
char orginal[N][100];
char required[N][100]; int main()
{
int T;
scanf("%d", &T); getchar();
while(T--)
{
int n, i, j;
scanf("%d", &n); getchar();//忽略换行,不然gets会返还空串
for(i=0; i<n;i++)
{
gets(orginal[i]);
}
for(i=0; i<n;i++)
{
gets(required[i]);
} for(i=j=n-1; i>=0;i--)
{
if(!strcmp(orginal[i], required[j]))
j--;
} for(;j>=0;j--)
puts(required[j]);
printf("\n"); } return 0;
}

uva 10152 ShellSort的更多相关文章

  1. uva 10152 ShellSort 龟壳排序(希尔排序?)

    今天状态总是很糟,这种题目卡了一天... 是不是休息时间太少了,头脑迟钝了... 名字叫希尔排序,我还以为跟它有关,还搜索了下资料. 只要找到trick就会发现是很水的题目.只要对比下就能找到哪些是移 ...

  2. UVA题目分类

    题目 Volume 0. Getting Started 开始10055 - Hashmat the Brave Warrior 10071 - Back to High School Physics ...

  3. (Step1-500题)UVaOJ&plus;算法竞赛入门经典&plus;挑战编程&plus;USACO

    http://www.cnblogs.com/sxiszero/p/3618737.html 下面给出的题目共计560道,去掉重复的也有近500题,作为ACMer Training Step1,用1年 ...

  4. ACM训练计划step 1 &lbrack;非原创&rsqb;

    (Step1-500题)UVaOJ+算法竞赛入门经典+挑战编程+USACO 下面给出的题目共计560道,去掉重复的也有近500题,作为ACMer Training Step1,用1年到1年半年时间完成 ...

  5. 算法竞赛入门经典&plus;挑战编程&plus;USACO

    下面给出的题目共计560道,去掉重复的也有近500题,作为ACMer Training Step1,用1年到1年半年时间完成.打牢基础,厚积薄发. 一.UVaOJ http://uva.onlinej ...

  6. 刘汝佳 算法竞赛-入门经典 第二部分 算法篇 第六章 1(Lists)

    127 - "Accordian" Patience 题目大意:一个人一张张发牌,如果这张牌与这张牌前面的一张或者前面的第三张(后面称之为一位置和三位置)的点数或花式相同,则将这张 ...

  7. ShellSort uva

    ShellSort He made each turtle stand on another one's back And he piled them all up in a nine-turtle ...

  8. uva 1354 Mobile Computing ——yhx

    aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABGcAAANuCAYAAAC7f2QuAAAgAElEQVR4nOy9XUhjWbo3vu72RRgkF5

  9. UVA 10564 Paths through the Hourglass&lbrack;DP 打印&rsqb;

    UVA - 10564 Paths through the Hourglass 题意: 要求从第一层走到最下面一层,只能往左下或右下走 问有多少条路径之和刚好等于S? 如果有的话,输出字典序最小的路径 ...

随机推荐

  1. 基于requests实现极客学院课程爬虫

    背景 本文主要是为了完成极客学院课程<Python 单线程爬虫>中讲师布置的实战作业. 开发环境 操作系统:windows 10 Python :Python 2.7 IDE:PyChar ...

  2. Windows下安装Maven

    上篇文章刚说到Linux下安装maven的过程,有时候为了适合在本地构建项目开发,然后上传到远程服务器执行,需要在本地构建maven项目,那么一般就是在Windows下构建maven项目并导入到我们的 ...

  3. &OpenCurlyDoubleQuote;康园圈--互联网&plus;校园平台&OpenCurlyDoubleQuote;项目之sprint1总结

    一.团队成员     梁植淋,官郅豪,纪焓,詹耀海 二.目前进度       在全体组员的努力下,目前完成了项目的<设计方案书>.<功能需求书>.框架搭建.项目部署文档. 并成 ...

  4. timeSeries db之:使用Metrics监控应用程序的性能 &lpar;zz&rpar;

    在编写应用程序的时候,通常会记录日志以便事后分析,在很多情况下是产生了问题之后,再去查看日志,是一种事后的静态分析.在很多时候,我们可能需要了解整个系统在当前,或者某一时刻运行的情况,比如当前系统中对 ...

  5. CI中写原生SQL&lpar;封装查询&rpar;

    封装查询 封装,通过让系统为你组装各个查询语句,能够简化你的查询语法.参加下面的范例: $sql = "SELECT * FROM some_table WHERE id = ? AND s ...

  6. Tomcat的测试页打开空白页的解决方法

    win7下安装tomcat 9简要步骤: 1.下载Tomcat 到Tomcat官网https://tomcat.apache.org/download-90.cgi下载Tomcat 9.0>Co ...

  7. java数组初始化的三种方式

      //第一种 int[] is= new int[3]; is[0]=1; is[1]=2; is[2]=3; //第二种 int[] is2= {1,2,3}; //第三种 int[] is3= ...

  8. 这种写法用过没:string&period;Format&lpar;&quot&semi;&lbrace;0&comma;-10&rcub;&quot&semi;&comma; 8&rpar;

    1 2 3 4 var s1 = string.Format("{0,-10}", 8); var s2 = string.Format("{0,10}", 8 ...

  9. Objective-C中的&commat;Property详解

    Objective-C中的@Property详解 @Property (属性) class vairs 这个属性有nonatomic, strong, weak, retain, copy等等 我把它 ...

  10. 【转载】在Linux下,一个文件也有三种时间,分别是:访问时间、修改时间、状态改动时间

    在windows下,一个文件有:创建时间.修改时间.访问时间.而在Linux下,一个文件也有三种时间,分别是:访问时间.修改时间.状态改动时间. 两者有此不同,在Linux下没有创建时间的概念,也就是 ...