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

我遇到了一个问题，需要程序计算一个区间内的点数。这个问题提供了大量未排序的点，以及lo,hi(restriction lo

 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;

最佳答案

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

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

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

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

关于c++ - 计算线间隔中的点数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34647051/