c++ - 计算线间隔中的点数

Question

我遇到了一个问题，要求程序计算一个区间内的点数。本题提供了大量未排序的点，且lo,hi(限制lo<=hi)，目的是枚举[lo,hi]内的点。问题是虽然我的代码是正确的，但是在给定的时间(2200ms)内完成太耗时了。我的代码可以在 O(n) 内完成这个任务。请问有没有更快的方法。

 int n,m,c,lo,hi;
    cin>>n>>m;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cin>>lo>>hi;
    c=0;
    for(int j=0;j<n;j++){
        if(arr[j]<=hi&&lo<=arr[j])c++;
    }
    cout<<c<<endl;

Answer 1

不可能在 O(n) 时间内解决这个问题，因为您必须至少考虑所有输入一次。

但是，您可以减少 n 的常数因子——您是否考虑存储一组 (start, end) 间隔，而不是一个简单的数组？导致速度变慢的输入大小是多少？

编辑:经过进一步测试，瓶颈似乎实际上是使用 cin 读取数字。

尝试将 cin >> x; 的每个实例替换为 scanf("%d", &x); — 对我来说，这将运行时间降低到大约 0.08秒。