codeforces A. Chess Placing
题目链接:
http://codeforces.com/contest/985/problem/A
题目大意如下:
一串大小为n的数字,给你n/2的数字,让你把这些数字全部变成奇数或者偶数,求最小的变化次数。
可以发现,即使数字前面有数字,不影响移动的次数。
我们假设,将全部的数字变成偶数,那么距离第i个数字最近的偶数为2*i,计算最近的距离即为 abs(2*i-a[i])
将偶数和奇数均计算一次,比较两种方式的最小值即可。
#include<bits/stdc++.h> using namespace std; int main() { int n,a[150]; scanf("%d",&n); for(int i=1;i<=n/2;i++) { scanf("%d",&a[i]); } int ans1=0,ans2=0; sort(a+1,a+n/2+1); for(int i=1;i<=n/2;i++) { ans1+=abs(2*i-1-a[i]); ans2+=abs(2*i-a[i]); } int ans=min(ans1,ans2); printf("%d ",ans); return 0; }
以后做这种数字规律题可以把最后的情况列出来,考虑现有情况与最终情况之间的差异,从而找到规律。