当前位置：首页 → 问答吧 → 紧急紧急~~~~这个程序怎么写。。。

紧急紧急~~~~这个程序怎么写。。。

时间：2011-12-19

来源：互联网

每天下课老师都会给某个学生进行课外辅导。由于时间有限，
所以老师只能辅导一名知识掌握程度最低的同学。如果有多名同学知识掌握程度最低，则
选编号最小的同学进行辅导。该同学在接受辅导后提升了知识掌握程度。老师想知道他每
天辅导的同学的编号。

★数据输入

输入第一行包括一个正整数N （1<=N<=50000），表示学生人数，第二行输入N 个正整
数，依次表示编号为从 1 到N 的同学的初始知识掌握程度。第三行输入一个正整数 m
（1<=m<=50000）,表示老师辅导了m 天。第四行输入m 个数，第i个数表示第i天接受辅导
的同学提升的知识掌握程度的值。

★数据输出

输出两个数，以一个空格隔开，表示m 天后知识掌握程度最低的同学的编号和知识掌
握程度。

输入示例输出示例
3 2 3
2 3 1
3
1 2 3

大神们~~~不能超时啊。。跪求。。自己写了几个都超时了。。。

无奈啊。。急呀。。

作者: luoxi_123123 发布时间: 2011-12-19

蛋疼贴

作者: youkuxiaobin 发布时间: 2011-12-19

楼主，输入输出，可否写清楚些，我怎么没看明白例子；

作者: liuliufen 发布时间: 2011-12-19

是输入是
3
2 3 1
3
1 2 3
吗？

作者: liuliufen 发布时间: 2011-12-19

不是。。。所谓的掌握度要怎么确定呢？用随机生成吗？

作者: yingzijuntuan 发布时间: 2011-12-19

这个问题，用堆排序做吧；

刚开始，建一个小顶堆，按照每个同学的初始掌握度和编号来排序，建好堆后，将堆顶同学掌握度加上这天老师辅导提升的知识掌握度，然后再调整堆到小顶堆，这样重复做m次，就得到了一个以知识掌握度和编号的小顶堆；这样再根据编号来排个序，就可以了；

时间复杂度是m * log(n) + nlog(n) ;

应该不会超时的；

作者: liuliufen 发布时间: 2011-12-19

引用 3 楼 liuliufen 的回复:

是输入是
3
2 3 1
3
1 2 3
吗？

抱歉哈。是的。。。那个是输入。。输出是 2 3

作者: luoxi_123123 发布时间: 2011-12-19

引用 5 楼 liuliufen 的回复:

这个问题，用堆排序做吧；

刚开始，建一个小顶堆，按照每个同学的初始掌握度和编号来排序，建好堆后，将堆顶同学掌握度加上这天老师辅导提升的知识掌握度，然后再调整堆到小顶堆，这样重复做m次，就得到了一个以知识掌握度和编号的小顶堆；这样再根据编号来排个序，就可以了；

时间复杂度是m * log(n) + nlog(n) ;

应该不会超时的；

能不能麻烦写一下，赶着交作业~~实在写不出，写了几个要不超时要不就错误了。

作者: luoxi_123123 发布时间: 2011-12-19