糖逗 发表于 2020-5-13 16:18:49

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

本帖最后由 糖逗 于 2020-5-13 16:29 编辑

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

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    int number, ask;
    cin >> number >> ask;
    vector<int> input1, input2;
    int temp;
    for(int i = 0; i < number; i++){
      cin >> temp;
      input1.push_back(temp);
    }
    int store;
    sort(input1.begin(), input1.end(), greater<int>());
    while(ask--){
      cin >> temp;
      store = 0;
      for(int i = 0; i < input1.size(); i++){
            if(input1 >= temp){
                store++;
                input1--;
            }
            else break;
      }
      cout << store << endl;
    }
    return 0;
}


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

糖逗 发表于 2020-5-13 16:21:36

这题还有时间更节约的方法吗？欢迎讨论{:10_324:}

shark1996 发表于 2020-5-13 16:44:15

本帖最后由 shark1996 于 2020-5-13 16:49 编辑

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

糖逗 发表于 2020-5-13 17:02:23

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

应该不是吧，主要是我写的这个是O(n^2)复杂度，想看看大家有没有时间复杂度更低的方案。
页: [1]
查看完整版本: C++刷笔试（序列维护）【数据结构】【网易】【2020】