描述
Mr. Wysuperfly uses a messenger tool called NKQQ to communicate with his friends on the net. The NKQQ accumulates 1 point score every hour automatically. When the score reach certain level, there will be a level-up. The relationship between the score and the level is listed as below:
| Level 1 | 0 － 100 |
| Level 2 | 101 － 500 |
| Level 3 | 501 － 2000 |
| Level 4 | 2001 － 10000 |
| Level 5 | 10001 － 50000 |
| Level 6 | 50001 － 200000 |
| Level 7 | 200001 － infinity |
Mr. Wysuperfly finds that other ACM teammates also use NKQQ everyday like him. He wants to know that after several hours, how many teammates reach a certain level. Can you help him?
输入
The first line is an integer N (N<=10^5) which represents the amount of the teammates to be considered. The second line includes N numbers which represent the scores of the teammates. The third line is a positive integer Q (Q<=10^5) which represents how many questions in the input data. In the following Q lines, each line which includes two integers D (0<=D<=10^9) and L (1<=L<=7) stands for a question: ‘After D hours, how many teammates will reach level L?
输出
For every question, output one line to show the answer to the question (one nonnegative integer).
样例输入
样例输出
题目意思：一小时加一分 问几小时后 在某一等级里分数有多少个。
解题思路： 二分查找。 查找某一区间里面个数
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5; 4 int t,D,L,L1,L2; 5 vector<int> vec; 6 int main() 7 { 8 ios::sync_with_stdio(false); 9 cin>>t; 10 for(int i=1,d;i<=t;i++) cin>>d,vec.push_back(d); 11 sort(vec.begin(),vec.end()); 12 cin>>t; 13 while(t--){ 14 cin>>D>>L; 15 if(L==1) L1=0,L2=100; 16 if(L==2) L1=101,L2=500; 17 if(L==3) L1=501,L2=2000; 18 if(L==4) L1=2001,L2=10000; 19 if(L==5) L1=10001,L2=50000; 20 if(L==6) L1=50001,L2=200000; 21 if(L==7) L1=200001,L2=1e10+5; 22 L1=L1-D,L2=L2-D; 23 int w1=lower_bound(vec.begin(),vec.end(),L1)-vec.begin(); 24 int w2=upper_bound(vec.begin(),vec.end(),L2)-vec.begin(); 25 cout << w2-w1 << endl; 26 } 27 }