http://poj.org/problem?id=3670
Eating Together
Time Limit:1000MS |
|
Memory Limit:65536K |
|
|
|
Description
The cows are so very silly about their dinner partners. They have organized themselves into three groups (conveniently numbered 1, 2, and 3) that insist upon dining together. The trouble starts when they line up at the barn to enter the feeding area.
Each cowicarries with her a small card upon which is engravedDi(1 ≤Di≤ 3) indicating her dining group membership. The entire set ofN(1 ≤N≤ 30,000) cows has lined up for dinner but it's easy for anyone to see that they are not grouped by their dinner-partner cards.
FJ's job is not so difficult. He just walks down the line of cows changing their dinner partner assignment by marking out the old number and writing in a new one. By doing so, he creates groups of cows like 111222333 or 333222111 where the cows' dining groups are sorted in either ascending or descending order by their dinner cards.
FJ is just as lazy as the next fellow. He's curious: what is the absolute mminimum number of cards he must change to create a proper grouping of dining partners? He must only change card numbers and must not rearrange the cows standing in line.
Input
* Line 1: A single integer:N
* Lines 2..N+1: Lineidescribes thei-th cow's current dining group with a single integer:Di
Output
* Line 1: A single integer representing the minimum number of changes that must be made so that the final sequence of cows is sorted in either ascending or descending order
Sample Input
5
1
3
2
1
1
Sample Output
1
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
选择了三道经典的二分查找的poj模拟题,有利于读者对二分查找的深刻把握
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
北大POJ1836-Alignment【O(nlogn)】
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ1002-487-3279【Hash+Qsort】 解题报告+AC代码
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ中级搜索全部练习【解题报告+AC代码】
用贪心算法解决POJ 1065的木棍处理问题
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码