英文原题 中文题译
题目大意是:给定一个由数字123构成的数列,最少多少次交换可以使得其变成升序序列。
以前做过POJ上的USACO题中有类似的,大意是给定123的序列,不交换,但可改变数字的值,问至少要改变多少个值使得整个序列有序。比这个略难些。对此题,扫描整个数列,得到每个数字区间的位置,考虑到首先所有的在23区间的1必须交换回1区间,然后考虑这样的交换会导致多少3跑到区间2中。注意n_i_j中存在一些等式,所以计算不难。
可将此题推广,在长为N的序列中有M个数,最少多少交换可使得序列变成升序。这样,第一部分基本不变,需要N×M的数组来记录数字位置,如果N×M很大,则可以两次扫描,第一次扫描得到每个数字的位置,第二次扫描用M×M数组(M×(M-1)/2就够)存放错位情况即:数字j在区间i中出现的个数。然后M循环,首先把数字1放在区间1内,逐个更新余下的错位数,然后数字2,....。算法的时间复杂度为O(N*M+M^3),考虑到一般M<<N,故依然为O(N*M),不过编程复杂度集中在后部。
题目大意是:给定一个由数字123构成的数列,最少多少次交换可以使得其变成升序序列。
以前做过POJ上的USACO题中有类似的,大意是给定123的序列,不交换,但可改变数字的值,问至少要改变多少个值使得整个序列有序。比这个略难些。对此题,扫描整个数列,得到每个数字区间的位置,考虑到首先所有的在23区间的1必须交换回1区间,然后考虑这样的交换会导致多少3跑到区间2中。注意n_i_j中存在一些等式,所以计算不难。
可将此题推广,在长为N的序列中有M个数,最少多少交换可使得序列变成升序。这样,第一部分基本不变,需要N×M的数组来记录数字位置,如果N×M很大,则可以两次扫描,第一次扫描得到每个数字的位置,第二次扫描用M×M数组(M×(M-1)/2就够)存放错位情况即:数字j在区间i中出现的个数。然后M循环,首先把数字1放在区间1内,逐个更新余下的错位数,然后数字2,....。算法的时间复杂度为O(N*M+M^3),考虑到一般M<<N,故依然为O(N*M),不过编程复杂度集中在后部。
/* ID: blackco3 TASK: sort3 LANG: C++ */ #include <fstream> using namespace std; #define _max_ 1000 int main() { ifstream fin("sort3.in"); ofstream fout("sort3.out"); int n_digit, n_dig[3]={0, 0, 0}, count[3][_max_+1]={{0}, {0}, {0}}, cur ; fin >> n_digit ; for( int i=1; i<=n_digit; i++ ){ fin >> cur ; for( int j=0; j<3; j++){ count[j][i] = count[j][i-1] + (j==cur-1) ; n_dig[j] += (j==cur-1) ; } } int n21=count[1][n_dig[0]]; /* how many 2 in segment 1 */ int n31=count[2][n_dig[0]]; /* how many 3 in segment 1 */ int n12=count[0][n_dig[0]+n_dig[1]]-count[0][n_dig[0]]; /* how many 1 in segment 2 */ int n32=count[2][n_dig[0]+n_dig[1]]-count[2][n_dig[0]]; /* how many 3 in segment 2 */ fout << (n21 + n31) + (n32 + n12 - (n12<n21 ? n12 : n21)) << endl ; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 888英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1136英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1852郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1647英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1200英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 975英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1074英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1408英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 786英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 801英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 976英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1211英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 919英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1097英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 778英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1235英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1051英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 934英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1312英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 871英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ...
相关推荐
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
USACO全部译题 USACO Training Program Gateway
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco2.1解题报告1
USACO全部题目官方分析翻译1993-1996美国计算机程序设计竞赛
pku acm上的一系列usaco题目都可以在这里找到测试数据以及源代码,不过题目的名字和pku上有得有点出入,需要自己去比较一下,2002年
2.1 Section 2.1 2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 3.1 Section 3.1 3.2 Section 3.2 3.3 Section 3.3 3.4 Section 3.4 4 Chapter4 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 ...
pku acm上的一系列usaco题目都可以在这里找到测试数据以及源代码,不过题目的名字和pku上有得有点出入,需要自己去比较一下,2001年
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO_培训USACO_培训Ride.java-> Gift1.java->
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
[USACO 1.1.4]破碎的项链.cpp
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO training 教程翻译合集(清晰明确)
USACO题目,Greedy Gift Givers