l5213. 玩筹码

  这道题本应该很简单的但是我把他复杂化了,所以没有在第一时间里A出来。我们来看看题目

l5213. 玩筹码

 

看上去是不是很复杂,思路是有,但是,很难实现。我最开始的时候是认为有三种情况,左边筹码最多,右边筹码最多,中间筹码最多。写了三组 for 循环。只过了70%的样例。这时候,我就意识到,我肯定想多了!当我重新思考这道问题的时候,我发现其实就只有两种情况:

   1、奇数点的筹码移动到偶数上,移动奇数次。

   2、偶数点的筹码移动到奇数上,移动偶数次。

为什么成立呢?因为我们规定了数轴为整数。所以我们选择的最终目的地不是奇数就是偶数。而且:

  设a属于奇数序列,那么必有 ai + 2*n = ai+n 

同样的,

  若b属于偶数序列,那么必有 bi + 2*n = bi+n 

这样很明显的就可以看出,移动次数只和奇、偶数相关。而且无论如何移动我最少移动次数也应该是奇或偶数的个数。所以统计一下奇数偶数的个数即可得出答案。

  这道题比较简单,先自己写,再看代码。

l5213. 玩筹码
 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

 

  周赛不易,诸君共勉!

上一篇:解决事件冒泡


下一篇:1295. Find Numbers with Even Number of Digits