标签：约翰 奶牛 int 18709 魔法 mw include

Description

农夫约翰的奶牛场有很多奶牛，奶牛有黑白两种颜色。现在奶牛们排成整齐的一列去参加镇上的游行活动。
约翰希望白色奶牛都排在前面，黑色的奶牛都排在后面。但现在队列中奶牛的颜色是混乱的，并且奶牛们都不愿意改变位置。
幸运的是，约翰有一根魔法棒，每挥舞一次魔法棒就可以改变一头奶牛的颜色。
请问，约翰至少要挥舞多少次魔法棒，才能将队列改成他希望的状态。注意，可以将所有的奶牛都变成白色，或者都变成黑色。

输入格式

第一行一个正整数n，表示奶牛的头数。(1<=n<=200000)。
第二行n个正整数，均为1或2，1表示白色奶牛，2表示黑色奶牛。

输出格式

一个正整数，表示挥舞魔法棒的最少次数。

 

输入样例

7
2 2 1 1 1 2 1

 

输出样例

3

 

提示

可以把1和2号奶牛变成1,7号奶牛变成2，或者全部奶牛变成1，最少需要3次。

 

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int n=0;
11     int i=0;
12     scanf("%d",&n);
13     int a[n];
14     int b[n]= {0},w[n]= {0},sum[n]= {0};
15     int min=0;
16     int mb=0,mw=0;
17     //数组a放输入数据
18     for(i=0; i<n; i++)
19     {
20         scanf("%d",&a[i]);
21     }
22     //数组b存的是：从前往后遍历a情况下，黑改白的次数前缀和
23     for(i=0; i<n; i++)
24     {
25         b[i]=mb;
26         if(a[i]==2)mb++;
27     }
28     //数组w存的是：从后往前遍历a情况下，白改黑的次数前缀和
29     for(i=n-1; i>=0; i--)
30     {
31         if(a[i]==1)mw++;
32         w[i]=mw;
33     }
34     for(i=0; i<n; i++)
35     {
36         sum[i]=b[i]+w[i];
37         if(i==0)min=sum[i];
38         if(min>sum[i])min=sum[i];
39     }
40     cout<<min;
41     return 0;
42 }

 

标签：约翰,奶牛,int,18709,魔法,mw,include
From： https://www.cnblogs.com/lw-sin/p/16901085.html