题解CF123A【Chips Moving】

题目大意:

给你$n$个点,每个点在一条数轴上,其坐标为$a_i$ ,将$a_i\pm1$需要一个代价

而将$a_i\pm2$无需代价

求出将所有点移到同一个点的最小代价(注意:该点可以为$0$,负数)

显然,一道水题

怎么做呢?由于$\pm2$无需代价,因此不考虑含有$2$的部分,也就是只考虑奇偶性

然而在把所有点都变成$0$或$1$之后,如何求答案呢?

显然,必然是将$0$全部移到$1$或者$1$全部移到$0$

取二者最小值即可

具体步骤:

  1. 每个点判奇偶,如为奇,则$++x$,否则$++y$
  2. 取$x,y$的最小值输出即可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
#define reg register
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define input(a){a=0;char c=gc();int f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}while(c>='0'&&c<='9'){a=(a<<3)+(a<<1)+(c&15);c=gc();}a*=f;}
static char buf[1<<21],*p1=buf,*p2=buf;
char bu[1<<21],cha[20];int p,pp=-1;
#define flush(){fwrite(bu,1,pp+1,stdout),pp=-1;}
#define output(x){if(pp>1<<20)flush();if(x<0)bu[++pp]=45,x=-x;do{cha[++p]=x%10+48;}while(x/=10);do{bu[++pp]=cha[p];}while(--p);}
#define Endl bu[++pp]='\n'
#define Space bu[++pp]=' '
#define pc(c) bu[++pp]=c
const int N=100010;
//以上请忽略
int n,a,x,y;
int main()
{
input(n);
for(;n;--n){input(a);a&1?++x:++y;}
//如果为奇,++x,否则,++y
x=min(x,y);
//取最小值
output(x);
//输出
flush();
return 0;
}
0%