第五届华为“创新杯”编程大赛初赛题目(第二场)

接上一篇帖子

第一题:密码合法性校验(点击展开)


感觉就是简单的匹配,自己代码结果未知

第一题自己的代码

第二题:把数组排成最小的数


一开始想着,就是把数当字符串来排序输出就行了
多想一下,发现其实是很复杂的问题,例如{21,2}就应输出212,而非按字典序的221
网上搜了下,是百度09年的面试题
大体思路依然是字符串排序,只不过在决定A,B次序时,只需比较AB、BA这两个字符串哪个更小,若AB小于BA,则在最小序列里,A一定在B的前面。
证明看网上写了一大堆,真啰嗦。我认为,若AB小于BA,则对于任意串x,y,z,显然有xAyBz小于xByAz,有这个结论就足够了。
不过这个思路实在是很难想到。

第二题自己的代码

第三题:以最节省的方式完成全程


完全没思路的一道题,一开始还想dp做的,但是状态不太好写(到达某站点下的最小代价和剩余电力都要考虑,多了的电又不能换钱)
后来就用如下土策略试试:
到达某站时:
1.如果剩余电量能到达后面电力更便宜的一个站,就开过去
2.如果1不符合,但是如果能够在该站加电,到达后面电力更便宜的一个站,就加电开过去,使得抵达时电力恰好用完
3.如果1,2都不符合,就在这个站加满电,然后跑到下一个站。若能抵达终点,就直接到终点
没法证明最优解,不过居然AC了

第三题自己的代码

一条评论

  1. Mickey 说道:

    你要是参加第二场就好了。PS:贴源码要有注释,3Q。

Mickey 进行回复 取消回复

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>