题目链接:http://codeforces.com/problemset/problem/371/A
题目意思:给出n和k和一个只有1或者2组成的序列,需要求出最少的改变次数,使得 n/k 组里面的数完全相等。如果该序列n/k组里面的数本来已经全部相等,输出0。
我的做法是,在这个序列中,找出n/k对应位置的数,统计1和0的个数。以第一组数据样例来说(n/k = 3组数,每组数用 "|" 隔开),
序号i : 1 2 | 3 4 | 5 6
对应的序列: 2 1 | 2 2 | 2 1
即分别统计1、3、5和2、4、6对应的2和1的个数,如果2的个数比较多,就把1的个数全部变为2,反之把2的个数转换成1(2、4、6的情况:cnt1= 1 ,cnt2 = 2,把1换成2,一次即可),这样能保证每次转换用的都是最少的次数,构造出的最终结果也是最少的。特别要注意,如果1的个数或者2的个数为0,此时不需要转换!
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 100 + 5; 8 int a[maxn]; 9 int c[3]; 10 11 int main() 12 { 13 int n, k, i, j, sum; 14 while (scanf("%d%d", &n, &k) != EOF) 15 { 16 for (i = 1; i <= n; i++) 17 scanf("%d", &a[i]); 18 sum = 0; 19 for (j = 1; j <= k; j++) 20 { 21 memset(c, 0, sizeof(c)); 22 c[a[j]] = 1; // 第一组数的每个数直接赋为1 23 for (i = j+k; i <= n; i += k) // 每组数统计对应位置1和2的个数 24 c[a[i]]++; 25 if (c[1] == 0 || c[2] == 0) 26 sum += 0; 27 else if (c[1] < c[2]) 28 sum += c[1]; 29 else 30 sum += c[2]; 31 } 32 printf("%d ", sum); 33 } 34 return 0; 35 }