| 题目名称 | 1069. [焦作一中2012] 吉他 |
|---|---|
| 输入输出 | gitara.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-09-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：22， 提交：38， 通过率：57.89% | ||||
 苏轼 |
100 | 0.349 s | 4.13 MiB | C++ |
 NARUTO |
100 | 0.350 s | 4.13 MiB | C++ |
 Cloud |
100 | 0.379 s | 0.31 MiB | C++ |
 WHZ0325 |
100 | 0.417 s | 0.31 MiB | C++ |
 kingshao |
100 | 0.453 s | 11.61 MiB | Pascal |
|
kingshao |
100 | 0.455 s | 7.03 MiB | Pascal |
 cstdio |
100 | 0.464 s | 0.31 MiB | C++ |
 cwystc |
100 | 0.464 s | 7.03 MiB | Pascal |
 王者自由 |
100 | 0.485 s | 0.30 MiB | C++ |
 ConanQZ |
100 | 0.490 s | 13.52 MiB | Pascal |
| 本题关联比赛 | |||
| 20120907 | |||
| 关于 吉他 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
ConanQZ
2017-10-31 22:33
2楼
| ||||
|
众大神是怎么写滴？？？？本菜用了二分查找，效率怎么比最快的慢了一倍？？？
 天下第一的吃货殿下
2012-10-03 20:01
1楼
| ||||
(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.