| 题目名称 | 615. 韩国明星 |
|---|---|
| 输入输出 | star.in/out |
| 难度等级 | ★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2011-11-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：105， 提交：172， 通过率：61.05% | ||||
 new ioer |
100 | 0.156 s | 13.28 MiB | C++ |
 lzy |
100 | 0.168 s | 107.15 MiB | C++ |
 战魂银狼 |
100 | 0.171 s | 115.23 MiB | C++ |
|
lzy |
100 | 0.172 s | 107.15 MiB | C++ |
|
lzy |
100 | 0.173 s | 107.15 MiB | C++ |
 changer |
100 | 0.173 s | 107.60 MiB | C++ |
 邓璐 |
100 | 0.176 s | 107.60 MiB | C++ |
 wssssxc |
100 | 0.176 s | 120.95 MiB | C++ |
 hytzongxuan |
100 | 0.178 s | 32.84 MiB | C++ |
 _Itachi |
100 | 0.178 s | 105.67 MiB | C++ |
| 本题关联比赛 | |||
| 20111110 | |||
| 20111110 | |||
| 关于 韩国明星 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
map水过。。。
| ||||
|
手贱如我。
| ||||
|
STL: 老夫还能再战五百年
| ||||
|
居然数组开太大全绿了一次。。
话说Trie的数组开多大真没准 _Itachi
2016-07-31 14:37
7楼
| ||||
|
Trie+暴力记录+sort大法好。
| ||||
|
STL好评如潮
| ||||
|
3种方法。1.二分2.定义一个以字符串为下标的数组3.<set>平衡二叉树 我用的3....感觉2会更快一些QAQ
 raywzy
2013-10-01 19:21
4楼
| ||||
|
刚开始用的“字符长度排序”及“二分查找区间”，再用一个“排序”，结果和暴力是一样的，过四组。（即程序中的注释部分）
后改用“字符数组字典序排序”，加上“二分准确查找”，最后一个一样的“排序”，果然很快，0.662秒lu过，无压力。 （以上所谓“排序”均为“手动随机化有附带值快排”） （“二分查找区间”找到的是同一长度的字符数组的范围，“二分准确查找”找到的就是最终要找的那个字符数组） （不过字典树优化后其实应该可以更快的，不过在NOIP中其实完全可以用其他的东西来代替字典树，所以，在NOIP以后再学学字典树吧，毕竟是很好用的一种数据结构） | ||||
|
字典樹
| ||||
|
唉,比赛的时候数组开小了.....错了1组
1.字符串排序 2.二分查找,累加 3.累加后数据排序 4.输出 | ||||
雨季
Bokjan
NemoAre
核糖核酸
Truth.Cirno
Czb。
QhelDIV【问题描述】
在LazyCat同学的影响下，Roby同学开始听韩国的音乐，并且越来越喜欢H.o.T，尤其喜欢安七炫和Tony，可是，爱学习爱思考的Roby同学想，如果以后喜欢的韩星越来越多怎么办呢？Roby怎么知道Roby最喜欢谁呢（Roby都不知道谁知道呢。。。。）？
于是，Roby同学求助于你。
Roby首先会给你一张表，表上是所有他认识的韩星的名字，一开始他对所有韩星的好感度都为0。然后Roby会告诉你一些他对某个韩星的好感度变化。最后，请按照Roby对他们好感从大到小的顺序输出他们。
【输入格式】
第一行一个个数N，表示Roby知道的韩星数目。
后面有N行，表示每一个Roby认识的韩星的名字。
再下面一行一个数K。
接下来2*K行，每两行为一组，上面一行为韩星的名字Name，下面一行为好感度变化量Change。
【输出格式】
N*2行，依据韩星们的受Roby好感度从大到小的顺序输出，每两行为一组，第一行输出韩星的名字，第二行输出受Roby的好感度。
【输入样例】
3 HhIsaGay ZcLoveStudy OneBlueOne 5 ZcLoveStudy 100 OneBlueOne 8888 ZcLoveStudy 20 OneBlueOne 8888 HhIsaGay -1000
【输出样例】
OneBlueOne 17776 ZcLoveStudy 120 HhIsaGay -1000
【数据范围】
对于20%的数据，保证N<=100，K<=100。
对于40%的数据，保证N<=10000，K<=30000。
对于100%的数据，保证N<=100000 -8888<=Change<=8888 K<=100000.