在网上看到一道编程题,想了好久实在不会,来请教

骇客不会飞 发布于 2014/05/18 21:36
阅读 795
收藏 4
有一行彩色的棋子,每个棋子的颜色是k种颜色之一。你不能改变棋子的顺序,但是可以移走一些棋子。问至少移走多少个石子,才能使得两个同色得石子之间没有其他颜色的棋子? 输入格式: 多组数据,每组数据两行,第一行是两个整数n和k, 1<=n<=100, 1<=k<=5 下一行是n个在[1..k]范围内的正整数,代表每个棋子的颜色。 输出格式: 每组测试数据输出一行包含一个整数,表示至少移走的石子数。 注:可以移走第2个第7个棋子。 
挑战规则:  
输入样例 10 3 2 1 2 2 1 1 3 1 3 3 输出样例: 2
加载中
0
骇客不会飞
骇客不会飞
这是我在CSDN上看到的一道题,我不是伸手党,我自己思考了真的不会才会来请教,想了好久实在没办法 ,包含的情况太多了,各位大神能否分享一下你们高端的代码 ,小弟谢过
0
骇客不会飞
骇客不会飞
原网址 http://hero.csdn.net/拉到底最后一道题, 各位大神可以去挑战,挑战成功能否分享源码学习学习,或者说说思路也行
0
wharf_zhang
wharf_zhang
如果是我来写,就选择最简单最直观最好写的一种:先拿到第一行的数,作为数组的大小,定义该数组;然后把第二行的数据存入该数组;接着遍历测试;最后返回结果。遍历测试:复制建立数组的临时副本,取第i个元素,去掉所有不等于它的其它元素,记下这个删除总次数。(显然,可以通过记录已处理的元素的unique列表来优化一下,或者遍历前先把数组排序去重,或者用个字典代替副本数组,等等)
0
wharf_zhang
wharf_zhang
最后返回结果是最少删除次数
0
泡不烂的凉粉
泡不烂的凉粉
没懂题意, 又是石子,又是棋子,还有颜色,能细说一下题意不。
0
B
BlueWoods

我有一个想法,可以试试。

1. 预处理输入串,把相邻的颜色group在一起,并记录长度,那么2 1 2 2 1 1 3 1 3 3 会变成(2, 1), (1, 1), (2, 2), (1, 2), (3, 1), (1, 1), (3, 2);

2. 在第一个和最后一个group之间选出长度最小的group,比如(1,1), 判断其颜色是否和两边的颜色一致,有两种情况:

  2a. 左右两边的颜色一致,那么把这个group删掉,删除次数 + group 长度;

  2b. 左右不一致,那么选取下一个符合条件的group,重复step2;

3. 如果在step2里面没有删除任何group,那么得到的结果就是最后的结果,所有的颜色之间都不在有其他颜色;否则重复第二步。

可以试试。这个的时间复杂度大概在n * n * logn 吧。没有仔细算。

骇客不会飞
骇客不会飞
我去试试
hello_world_me
hello_world_me
思路很清晰。
0
RegnoiX
RegnoiX
记录每种颜色石头的数组索引,然后计算下 每种颜色石头需要删除的个数,然后取最小
0
hello_world_me
hello_world_me

参考一下这个:http://blog.csdn.net/mamihong/article/details/22752217

果真是理论知识少,根本无从下手啊。

骇客不会飞
骇客不会飞
回复 @hh_hpp_cxx :好的,我尽量吧, 唉,没学过算法,思考个题目真难
hello_world_me
hello_world_me
@骇客不会飞 写好了贴代码瞧瞧啊 !
骇客不会飞
骇客不会飞
真的是雪中送炭啊,谢谢谢谢
0
中山野鬼
中山野鬼

标准算法就是个深度(广度)优先的递归咯。。。扫描各种方法,然后选择最少步骤达到要求的。哈。

可优化的也是针对这个搜索策略,在中途做停止本策略继续扫描的判决条件。


返回顶部
顶部