C++刷笔试（序列维护）【数据结构】【网易】【2020】

糖逗

题目描述：如图1
题目来自：牛客网

1. #include <vector>
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main(void){
   
7.     int number, ask;
   
8.     cin >> number >> ask;
   
9.     vector<int> input1, input2;
   
10.     int temp;
    
11.     for(int i = 0; i < number; i++){
    
12.         cin >> temp;
    
13.         input1.push_back(temp);
    
14.     }
    
15.     int store;
    
16.     sort(input1.begin(), input1.end(), greater<int>());
    
17.     while(ask--){
    
18.         cin >> temp;
    
19.         store = 0;
    
20.         for(int i = 0; i < input1.size(); i++){
    
21.             if(input1[i] >= temp){
    
22.                 store++;
    
23.                 input1[i]--;
    
24.             }
    
25.             else break;
    
26.         }
    
27.         cout << store << endl;
    
28.     }
    
29.     return 0;
    
30. }

复制代码

注意事项：
1.先排序再计算

糖逗

这题还有时间更节约的方法吗？欢迎讨论

shark1996

是不是和你输入的ask值有关，它大于最大值，可以不做判断，

糖逗

shark1996 发表于 2020-5-13 16:44
是不是和你输入的ask值有关，它大于最大值，可以不做判断，

应该不是吧，主要是我写的这个是O(n^2)复杂度，想看看大家有没有时间复杂度更低的方案。