吐槽
滚动

2017 C语言积分赛 热身赛 C题 石化威廉 题解

题目描述

题目背景
漫长战斗终于分出胜负了。
“喂,我可没听说非拼成这样才赢得了。”
七道亡国级禁咒,十一把开刃到自毁程度的帕西瓦尔系列,甚至青年本身没资格动用的勇者剑技最终奥义都已经强行祭出。
假如这样还不能将其灭绝,也无计可施了。
「真是惊天动地啊。身为无力的凡人之躯,却能独自使出此等力量吗?实在可怕。不过,看来要发挥那样的力量,实在不可能毫无代价。」
“啪”的一声,青年脚踝前面的部分已经变成粗糙的石块了。
又是好几声脆响重叠在一起,灰色面积开始沿着他的身体往上蔓延扩散,到了膝盖,到了腿,到了腰,还在继续往上。

题目描述
威廉即将在t个单位时间内完全石化,现在他对往事无限怀念,希望尽可能多的想起重要的人。
威廉有n个重要的人,而每个单位时间里他同时只能想一个人。
在此时此刻,回想第i个重要的人有关的事情都要消耗p[i]的时间,且只有时间p[i]完全经过才算确实回想起这个人。
威廉该按什么顺序回想,才能尽可能多的回顾和重要的人经历的事情呢?

输入

第一行,包含两个正整数t,n。
接下来n行,每行包含一个字符串和一个正整数p[i]。其中字符串表示第i个重要的人的姓名。

每个字符串均不超过50个字符。
对于100%的数据,1<=t<=10000000,1<=n<=500000,1<=p[i]<=1000。

输出

输出按最佳回想顺序能想起的人数。

样例输入

样例输出

思路上依然是非常简单的一个裸的贪心题,按升序排个序,每次选取时间最小的就行了。

唯一坑点在于数据量太大,冒泡会超时。于是这里采用快速排序。

Code:

 

Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment