这道题本应该很简单的但是我把他复杂化了,所以没有在第一时间里A出来。我们来看看题目
看上去是不是很复杂,思路是有,但是,很难实现。我最开始的时候是认为有三种情况,左边筹码最多,右边筹码最多,中间筹码最多。写了三组 for 循环。只过了70%的样例。这时候,我就意识到,我肯定想多了!当我重新思考这道问题的时候,我发现其实就只有两种情况:
1、奇数点的筹码移动到偶数上,移动奇数次。
2、偶数点的筹码移动到奇数上,移动偶数次。
为什么成立呢?因为我们规定了数轴为整数。所以我们选择的最终目的地不是奇数就是偶数。而且:
设a属于奇数序列,那么必有 ai + 2*n = ai+n
同样的,
若b属于偶数序列,那么必有 bi + 2*n = bi+n
这样很明显的就可以看出,移动次数只和奇、偶数相关。而且无论如何移动我最少移动次数也应该是奇或偶数的个数。所以统计一下奇数偶数的个数即可得出答案。
这道题比较简单,先自己写,再看代码。
1 /** 2 * @brief 玩筹码 3 * @note 偷懒用了三目 4 * @param *chips: 数组 5 * @param chipsSize: 数组大小 6 * @author 杨文蓁的小迷弟 7 */ 8 int minCostToMoveChips(int *chips, int chipsSize) 9 { 10 int Odd = 0, Even = 0; 11 12 for (int i = 0; i < chipsSize; i++) 13 { 14 if (chips[i] & 1) 15 { 16 Odd++; 17 } 18 else 19 { 20 Even++; 21 } 22 } 23 24 return Odd > Even ? Even : Odd; 25 }View Code
周赛不易,诸君共勉!