网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[焦作一中2012]吉他
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | gitara.in | 输出文件 | gitara.out |
(gitara.pas/c/cpp)
【问题描述】
小x有一个神密的朋友: 一个外星人,这个外星人有无数个触角,还有一把很神奇的吉他。小x最近一个爱好就是听外星人弹吉他。
这个吉他和非常巨大,有6根弦,每根弦有P个品丝,编号为1..P,每根弦的每个品丝可以发出不同的乐音,且乐音的音调随着品丝的编号依次增加。
因为外星人有无数个触角,他可以触动很多个不同的品丝,来发出不同的乐音。这个吉他的神奇之处在于,如果外星人触动某根弦上多个品丝,它只会发出音调最高的乐音(品丝编号最高发出的乐音)。
现在,小x想让外星人朋友弹一首包含N个乐音的曲子,而外星人朋友则想让小x首先计算出他最少移动多少次触角能够完成这首曲子的弹奏。
【输入】
第一行包含两个整数:N和P,表示曲子有N个乐音,吉他的每根弦上有P个品丝。
接下来N行,每行两个整数xi和yi,表示第i个乐音需要触动第xi跟弦上的第yi个品丝。
【输出】
一个整数,表示最小的移动触角的次数。
【输入输出样例1】
gitara.in |
gitara.out |
5 15 2 8 2 10 2 12 2 10 2 5 |
7 |
【样例解释】 第一个乐音需要移动1次触角,第二个也是1次,第三个也是1次,第四次需要把编号为12的品丝松开,也是1次,第5次需要把编号为8,10的品丝松开,并触动编号为5的品丝,需要3次。所以一共是7次。
【输入输出样例2】
gitara.in |
gitara.out |
7 15 1 5 2 3 2 5 2 7 2 4 1 5 1 3 |
9 |
【样例解释】依次移动触角的次数是:1, 1, 1, 1, 3, 0, 2
【数据范围】
50% 数据保证 0<=N,P<=5000
100% 数据保证 0<=N<=500000 0<=P<=300000.