题目描述

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。

写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数

输入输出格式

输入格式:

第一行:

奖牌个数N (1 <= N <= 1000)

第 2行到第N+1行:

每行一个数字,表示奖牌。共N行。(1..3)

输出格式:

共一行,一个数字。表示排成升序所需的最少交换次数。

输入输出样例

输入样例#1: 复制

9
2
2
1
3
3
3
2
3
1
输出样例#1: 复制

4

说明

USACO 2.1

翻译来自NOCOW

思路:贪心。

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans;
int a[];
int num[],pos[];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&num[i]),pos[num[i]]++;
for (int i=;i<=pos[]+pos[];i++){
if(num[i]==) a[]++;
else if(num[i]==&&i<=pos[]) a[]++;
else if(num[i]==&&i>pos[]) a[]++;
}
cout<<a[]+(a[]>a[]?a[]:a[])<<endl;
}

最新文章

  1. CSS Sprite雪碧图应用
  2. Unity3d导出Android的apk文件时相关问题的解决办法
  3. ibatis中iterate的用法(conjunction=&quot;or&quot; &quot;,&quot;)
  4. checkbox 全选/取消
  5. HDU5044---Tree 树链剖分
  6. 二、fragment使用
  7. Android - 采用ApiDemos得知Android开展
  8. ios 基础学习二
  9. 使用国内docker镜像源
  10. JVM 内存分配模型概念和java中各种对象的存储
  11. Django-Model操作数据库(增删改查、连表结构)
  12. Shiro笔记(二)身份验证
  13. vue elment-ui 样式替换 input select
  14. JavaScript 函数与对象的 简单区别
  15. ES6之Array.from()方法
  16. JavaScript 问题解决 -- parseInt(&quot;08&quot;)或parseInt(&quot;09&quot;)转换返回0的解决方法
  17. Ubuntu 配置网卡信息
  18. 洛谷P2051 [AHOI2009]中国象棋(dp)
  19. centos7 设置mongodb远程连接
  20. 【转】Jmeter变量参数化及函数应用

热门文章

  1. 欢迎访问微先锋vXianFeng官方博客
  2. luoguP1462通往奥格瑞玛的道路(二分答案+spfa)
  3. java源码学习
  4. Linux权限管理(用户、组、文件管理)
  5. MySQL好弱智的一个错误
  6. PHP 做图片锐化处理
  7. 动态限制EdiText仅仅能输入特定字符
  8. Redis封装之String
  9. js数组去重的常用方法总结
  10. WebAssembly学习(六):AssemblyScript - 限制与类型