题目要求简述:给定长度分别为n1,n2(n1,n2<=100)且每列的高度只为1或者2的长条。需要将他们放入一个高度为3的容器,问能够容纳它们的最短容器长度。
分析:
- 对于这样的题目显而易见有两种思路,第一,固定一个字符串,另一个从左到右进行移动。第二,固定一个字符串a,字符串b移动,再固定b,让a移动,取二者长度最小值。
- 两种方法我都经过自己的实现,觉得还是第二种代码更简洁优雅,同时还具有一定的可扩展性。
用例子说明一下吧~
数组1和数组2是我们待比较的两个数组,(当然,都是字符串数组),我们先固定其中的任意一个,放在下方,在让另一个在上方不断向左平移,进行比较,即可
当初次比较时,有如下图例
此时,从数组1的头元素开始和数组2的头元素进行比较,当出现两个2,或者匹配部分比较完成时,此次比较完成,用一个状态变量标记此次比较的结果。
由图例知,此次比较会停止在下标为1的元素上。
然后上面的数组下标右移,相当于数组左移,进行第二次比较。
由图例知,此次比较是成功的,用两个数组的总长度n1+n2减去匹配部分的长度,即得到此次所需的长度len,如果len小于原先记录的最小长度,则更新最小长度。
不断重复上述过程,直到这种情况为止:
这样我们就完成一半的比较任务,接下来,就是将数组1和数组2的位置颠倒,重复上述过程,取两次所得最小值,即可得到最终结果
颠倒并重复上述过程:
明白了思路,接下来让我们给出一个简洁的代码实现:
#include<cstdio>
#include<cstring>
const int maxn=;
char a[maxn+],b[maxn+];
int n1,n2;
int min(const int &i,const int &j){
return i<j?i:j;
}
int minLen(char *s1,char *s2,int &n){// n为s1的长度
int sumLen=n1+n2,minn=min(n1,n2),len=sumLen;
for(int i=;i<n;i++){
int ok=,fix=min(n-i,minn);//fix的计算是一个难点
for(int j=;j<fix;j++)if(s1[i+j]==''&&s2[j]==''){
ok=;break;
}
if(ok&&len>sumLen-fix)len=sumLen-fix;
}
return len;
}
int main(){
while(scanf("%s%s",&a,&b)==){
n1=strlen(a),n2=strlen(b);//无意中用到了逗号运算符
printf("%d\n",min(minLen(a,b,n1),minLen(b,a,n2)));//用min函数取两次结果的最小值
}
}
好啦,今天就到这里,贴一下战果以及传送门,大家加油哦~~~,拜拜\(•ω•`)o
题目传送门:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4463
第三章 数组与字符串 UVa1588 Kickdown的更多相关文章
-
JQuery攻略(三)数组与字符串
在上两章,JQuery攻略(一) 基础知识——选择器 与 DOM 和 JQuery攻略(二) Jquery手册 我们为后面的章节打好了基础,在这一章节中,我们继续. 在这一章节中,我们记录的是JQue ...
-
C语言 第七章 数组与字符串
一.数组 1.1.数组的概念 用来存储一组相同类型数据的数据结构.有点像班上放手机的手机袋,超市的储物柜. 特点:只能存放一种类型的数据,如全部是int型或者全部是char型,数组里的数据成为元素. ...
-
C++学习笔记(三)--数组、字符串
1.数组,C++中不允许数组的下标值为变量,只能是常量或者常量表达式,必须先定义后使用.数组赋初值几种常见方式: int a[] = {1,2,3,4,5}: int a[4] = {2,1,3,4} ...
-
快学Scala-第三章 数组相关操作
知识点: 1.定长数组 Array val nums = new Array[Int](10) //10个整数的数组,所有元素初始化为0 val a = new Array[String](10) / ...
-
PHP:第三章——数组中的array_values
例: <?php header("Content-Type:text/html;charset=utf-8"); //array_value(); //功能:返回数组中所有的 ...
-
快学Scala习题解答—第三章 数组相关操作
3 数组相关操作 3.1 编写一段代码.将a设置为一个n个随机整数的数组,要求随机数介于0(包括)和n(不包括)之间 random和yield的使用 import scala.math.rando ...
-
《Python基础教程》第三章:使用字符串
find方法可以在一个较长的字符串中查找子字符串.它返回子串所在位置的最左端索引.如果没有找到则返回-1 join方法用来在队列中添加元素,需要添加的队列元素都必须是字符串 >>> ...
- 《快学Scala》第三章 数组相关操作
-
java中的数据类型,运算符,字符串,输入输出,控制流,大数值,数组; 《java核心技术卷i》 第三章:java基本程序结构;
<java核心技术卷i> 第三章:java基本程序结构: 每次看书,去总结的时候,总会发现一些新的东西,这次对于java的数组有了更深的了解: java中的数据类型,运算符,字符串,输入输 ...
随机推荐
-
iOS - 用 UIBezierPath 实现果冻效果
最近在网上看到一个很酷的下拉刷新效果(http://iostuts.io/2015/10/17/elastic-bounce-using-uibezierpath-and-pan-gesture/). ...
-
Datastage数据装载报错:Consumed more than 1000000 bytes looking for record delimiter
使用Datastage装载数据时报错如下图: 使用ds进行数据传输时,出现上述问题,最终找到了问题的原因: 我所使用的数据文件比较大,上传到服务器的时候传了80%就出现服务器存储空间不够,我删除以前的 ...
-
hbase importtsv
hadoop jar hbase-server-0.98.1-cdh5.1.3.jar importtsv -Dimporttsv.columns=HBASE_ROW_KEY,cf:imsi,cf:i ...
-
Echarts数据可视化radar雷达坐标系,开发全解+完美注释
全栈工程师开发手册 (作者:栾鹏) Echarts数据可视化开发代码注释全解 Echarts数据可视化开发参数配置全解 6大公共组件详解(点击进入): title详解. tooltip详解.toolb ...
-
前端框架VUE----对象的单体模式
对象的单体模式 为了解决箭头函数this指向的问题 推出来一种写法 对象的单体模式 1 var person = { 2 name:'小马哥', 3 age:12, 4 fav(){ 5 consol ...
-
CMake Error at cmake/OpenCVModule.cmake:295 (message): No extra modules found in folder:Please provide path to &#39;opencv_contrib/modules&#39; folder
其实,我们使用的opencv中要用的contrib/modules 是需要额外下载并在cmakelists.txt中指定的 git clone https://github.com/opencv/ ...
-
【网络通讯】Nat知识了解
一.Nat的含义 NAT(Network Address Translation,网络地址转换)是1994年提出的.当在专用网内部的一些主机本来已经分配到了本地IP地址(即仅在本专用网内使用的专用地址 ...
-
python打造文件包含漏洞检测工具
0x00前言: 做Hack the box的题.感觉那个平台得开个VIp 不然得凉.一天只能重置一次...mmp 做的那题毒药是文件包含漏洞的题,涉及到了某个工具 看的不错就开发了一个. 0x01代码 ...
-
POJ 3553 Light Switching Game 博弈论 nim积 sg函数
http://poj.org/problem?id=3533 变成三维的nim积..前面hdu那个算二维nim积的题的函数都不用改,多nim积一次就过了...longlong似乎不必要但是还是加上了 ...
-
十六、dbms_space_admin(提供了局部管理表空间的功能)
1.概述 作用:提供了局部管理表空间的功能 2.包的组成 1).segment_verify作用:用于检查段的区映像是否与位图一致语法:dbms_space_admin.segment_verify( ...