奥是奥特曼的奥

玩筹码|奇偶位查找
题目描述数轴上放置了一些筹码,每个筹码的位置存在数组 chips 当中。你可以对 任何筹码 执行下面两种操作之一(...
扫描右侧二维码阅读全文
29
2019/10

玩筹码|奇偶位查找

题目描述

数轴上放置了一些筹码,每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一(不限操作次数,0 次也可以):

  1. 将第 i 个筹码向左或者右移动 2 个单位,代价为 0。
  2. 将第 i 个筹码向左或者右移动 1 个单位,代价为 1。

最开始的时候,同一位置上也可能放着两个或者更多的筹码。

返回将所有筹码移动到同一位置(任意位置)上所需要的最小代价。

输入

输入一个长度为n的序列(表示筹码的位置)

输出

输出一个值(表示最小代价)


示例 2:

输入:chips = [2,2,2,3,3]
输出:2
解释:第四和第五个筹码移动到位置二的代价都是 1,所以最小总代价为 2。


 

提示:

解题思路

在数轴上有一些筹码,输入他们的位置,找到移动的最小代价。
其中偶数位置的到偶数位置的没有代价,奇数到奇数位置的没有代价(比如位置1到位置3不需要代价,2到4也不需要)
那么在这个条件下就可以把所有奇数位置的筹码放到一个位置上(比如1,3,5三个位置上有一堆筹码,你可以全部堆在3位置上,反正不需要代价)
于是在没有代价的情况下,我们就可以把所有偶数位置的筹码和奇数位置的砝码摆到连续的位置上

其次,奇数到偶数和偶数到奇数的移动一个筹码就需要1代价
于是再比较两者中谁的数量比较少,少的一侧有多少砝码就是对应的总代价。

其实就是:遍历一次数组,找到其中有多少个奇数和偶数位置的砝码,取其中比较少的为答案

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int chip[maxn];

int main(){
    int n,x=0,y=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>chip[i];
        if(chip[i]%2==0){
            x++;
        }else{
            y++;
        }
    }
    cout<<min(x,y)<<endl;
    return 0;
}
Last modification:October 29th, 2019 at 09:13 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment