题目描述
为了避免餐厅过分拥挤, FJ 要求奶牛们分 2 批就餐. 每天晚饭前, 奶牛们都会在餐厅前排队入内, 按 FJ 的设想, 所有第 2 批就餐的奶牛排在队尾, 队伍的前半部分则由设定为第 1 批就餐的奶牛占据. 由于奶牛们不理解 FJ 的安排, 晚饭前的排队成了一个大麻烦.
第 i 头奶牛有一张标明她用餐批次 D_i(1≤D_i≤2) 的卡片. 虽然所有 N(1≤N≤30000) 头奶牛排成了很整齐的队伍, 但谁都看得出来, 卡片上的号码是完全杂乱无章的.
在若干次混乱的重新排队后, FJ 找到了一种简单些的方法: 奶牛们不动, 他沿着队伍从头到尾走一遍, 把那些他认为排错队的奶牛卡片上的编号改掉, 最终得到一个他想要的每个组中的奶牛都站在一起的队列, 例如 112222 或 111122. 有的时候, FJ 会把整个队列弄得只有 1 组奶牛 (比方说, 1111 或 222).
你也晓得, FJ 是个很懒的人. 他想知道, 如果他想达到目的, 那么他最少得改多少头奶牛卡片上的编号. 所有奶牛在 FJ 改卡片编号的时候, 都不会挪位置.
输入输出格式
输入格式
第一行, 一个整数 N.
第二至第 N+1 行, 第 i+1 行是一个整数, 为第 i 头奶牛的用餐批次 D_i.
输出格式
一行, 输出一个整数, 为 FJ 最少要改几头奶牛卡片上的编号, 才能让编号变成他设想中的样子.
输入输出样例
输入样例
- 7
- 2
- 1
- 1
- 1
- 2
- 2
- 1
输出样例
2
题解
虽然这题可以很轻松地用 dp 做出来, 但是还是打算介绍一种前缀和的做法.
只需要用前缀和统计到当前的数字 1 或 2 的出现次数, 然后枚举最后有几个数字 1, 利用前面的前缀和来算更改次数, 取最优值即可.
- #include<iostream>
- using namespace std;
- int n,temp,na[30005],nb[30005],mina=30005;
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>temp;
- if(temp==1) na[i]++;
- else nb[i]++;
- na[i]+=na[i-1];
- nb[i]+=nb[i-1];
- }
- for(int i=1;i<=n+1;i++)
- {
- if(na[n]-na[i-1]+nb[i-1]<mina) mina=na[n]-na[i-1]+nb[i-1];
- }
- cout<<mina;
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-2945126.html