18709 魔法

18709 魔法

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次。

作者 30002692


\#include <bits/stdc++.h> typedef long long ll; using namespace std; int n,a[200005],t[200005]; int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j,ans=200001; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; if(a[i]==2) t[i]=t[i-1]+1; else t[i]=t[i-1]; } for(i=1;i<=n;i++) ans=min(ans,t[i-1]+n-i-t[n]+t[i]); cout<<ans<<endl; return 0; }

Mark

不需要同时算黑牛和白牛的值,总数做差即可n-i-t[n]+t[i]

版权声明:本文为 溪月阁 | MoBrook 博主「 皓月 」的原创文章遵循用 CC BY-NC-SA 4.0 版权协议进行许可,转载请附上原文出处链接及本声明。

本文链接https://mobrook.cn/index.php/scau-18709/

上一篇:

下一篇: