UVA1588 换抵挡装置 Kickdown题目大意一家全球顶尖汽车企业的研究实验室接到订单需要研发一款特殊变速机构该机构能实现极高效的降挡操作切换至低速挡位。经过数月研究工程师发现最优方案需要使用齿和凹槽分布不均匀的特殊齿轮并且已经算出齿轮齿面的最优形态。现在他们需要开展实验来验证该结论。实验第一阶段采用平面齿状条块替代圆形齿轮。一段条块由 n 个单元组成每个单元要么是高度 h 的凹槽用字符 1 表示要么是高度 2h 的齿用字符 2 表示。实验需要两段条块一段模拟主动齿轮齿在下方一段模拟从动齿轮齿在上方。实验室有一条宽度固定为 3h 的长条合金材料长度足够长可以将两段条块错位拼接咬合放置在这条材料上。两段条块形状不规则但可以沿着水平方向互相偏移错开摆放。这种合金材料造价昂贵工程师希望尽可能减少材料使用量。你的任务是求出能同时放下两段条块所需的长条材料的最小总长度。两段条块咬合摆放的约束规则任意同一个水平位置上主动齿轮单元与从动齿轮单元不能同时都是齿数值 2。因为主动齿高度 2h 在下、从动齿高度 2h 在上两者叠加总高度会达到 4h超过材料固定宽度 3h发生冲突一个是齿一个是凹槽2 和 1、两个都是凹槽1 和 1都不会冲突可以正常摆放。两段条块不能翻转、不能旋转只能左右平移错开。输入输入包含多组测试用例每组用例两行输入第一行字符串代表主动齿轮条块第二行字符串代表从动齿轮条块。字符串中每个字符代表一个单元1是凹槽2是齿字符串不可翻转、旋转每个字符串非空长度不超过 100。输出针对每组测试用例输出一行一个整数代表摆放两段条块所需长条材料的最小长度。解题思路先把两段齿轮字符串读入初始最短长度设为两段完全分开拼接的总长先让下层齿轮向右逐步偏移偏移格数从 0 开始递增每偏移一格就核对重叠位置高度之和是否超过 3首个无冲突的偏移算出对应摆放长度并更新最短值直接停止该轮偏移遍历再换上层齿轮向右逐步偏移同样从 0 格开始依次校验重叠高度找到首个合规偏移更新最短长度全部偏移情况比对完成后输出最终最小摆放总长。完整代码importjava.util.Scanner;publicclassKickdown{publicstaticbooleancheckDownShift(Stringup,Stringdown,intk){intlenAup.length();intlenBdown.length();for(intj0;jlenB;j){intposkj;if(poslenA){break;}inthaup.charAt(pos)-0;inthbdown.charAt(j)-0;if(hahb3){returnfalse;}}returntrue;}publicstaticbooleancheckUpShift(Stringup,Stringdown,intk){intlenAup.length();intlenBdown.length();for(intj0;jlenA;j){intposkj;if(poslenB){break;}inthaup.charAt(j)-0;inthbdown.charAt(pos)-0;if(hahb3){returnfalse;}}returntrue;}publicstaticintminLength(Stringa,Stringb){intlenAa.length();intlenBb.length();intminTotallenAlenB;for(intk0;ka.length();k){booleanflagcheckDownShift(a,b,k);if(flag){intcurrentLonMath.max(lenA,lenBk);if(currentLonminTotal){minTotalcurrentLon;}break;}}for(intk0;kb.length();k){booleanflagcheckUpShift(a,b,k);if(flag){intcurrentLonMath.max(lenB,lenAk);if(currentLonminTotal){minTotalcurrentLon;}break;}}returnminTotal;}publicstaticvoidmain(Stringargs[]){ScannerscnewScanner(System.in);while(sc.hasNextLine()){Stringupsc.nextLine().trim();Stringdownsc.nextLine().trim();System.out.println(minLength(up,down));}sc.close();}}
