网站首页  |  业界新闻  |  技术文章  |  视频教程  |  下载频道  |  程序源码  |  个人空间  |  编程论坛
 
学习型 ASP/PHP/ASP.NET 主机 30元/年 全能 ASP/PHP/ASP.NET 主机,支持月付 专业 MSSQL 数据库空间,支持月付 专业 MySQL 数据库空间,支持月付
发新话题
打印

最佳通讯问题

最佳通讯问题

最近做了道题目,想找个O(N)的算法,不知道谁能解决下
A.    最佳通信工具——NKQQ
时间限制:1.5秒 内存限制:10000KB
Wysuperfly每天都会上网并使用一种网络通讯工具叫做NKQQ,NKQQ每小时自动增加积分1分,当积分达到一定程度的时候会升级。积分与级别对应如下:

等级 1    0 - 100
等级 2    101 - 500
等级 3    501 - 2000
等级 4    2001 - 10000
等级 5    10001 - 50000
等级 6    50001 - 200000
等级 7    200001 - 无穷

Wysuperfly发现南开ACM的许多队员也都同他一样天天24小时挂NKQQ,他很想知道过了若干小时之后,达到特定级别的队员有多少个。你能帮助他吗?
输入 (请使用标准输入输出,而不要读写文件)
第一行是一个正整数N (N<=100000)表示需要考虑的队员人数。第二行有N个数字,表示N个队员当前的积分。第三行是一个正整数Q (Q<=100000),表示有多少个问题,后面有Q行,每行两个整数D (0<=D<=109),L (1<=L<=7)代表一个问题:“D小时后,达到等级L的有多少个人?”
输出 (请使用标准输入输出,而不要读写文件)
  对于每个询问,输出一行,表示所询问的人数。
样例输入    样例输出
3
1 2 3
2
98 1
98 2    2
1

TOP

各个等级之间既不是等差,又不是等比,没法弄

TOP

呃。。。不就是已经O(n)了吗?请教一下怎么写O(n^2)或者O(nlogn)的?

by 雨中飞燕 C/C++学习群(TC勿进):57909089 46520219
C/C++学习网站: http://yzfy.org/

TOP

回复 3# 的帖子

我先把输入的数据先快排了一遍,然后在从小到大判断第一个到达这个等级的和最后一个满足这个等级的,然后求差得出结果,感觉还是不够快,汗,我菜菜

TOP

发新话题