~3 ccf 2022-03-2 出行计划

题目描述

输入

输出

样例输入

6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2

样例输出

3
3

源代码

70分 原因：错误

#include <iostream>

using namespace  std;


int main (){
    
    int n,m,k;
    cin>>n>>m>>k;
    int temp=0;
    int result=0;
    int *arrTime = new int [n];
    int *arrLimit = new int [n];
    int *sign= new int[m];
    bool ssi= true;
    for (int i = 0; i <n ; i++) {
    
        int g,h;
        cin>>g>>h;
        arrTime[i]=g;
        arrLimit[i]=h;
    }
    for (int i = 0; i < m; i++) {
    
        cin>>temp;
        ssi=true;
        int low, high, mid;
        low = 0;
        high =n - 1;
        while (low <= high) {
    
            mid = (low + high) / 2;
            if (arrTime[mid] < temp+k)
                low = mid + 1;
            else if (arrTime[mid] >temp+k)
                high = mid - 1;
            else{
    
                sign[i]= mid;
                ssi= false;
                break;
            }
        }
        if (ssi){
    
            sign[i]= mid;
        }
        for (int j = sign[i]; j <n ; j++) {
    
            if (arrTime[j] >= temp+k ){
    
                if (arrTime[j]<=temp+k+arrLimit[j]-1){
    
                    result++;
                }
            }
        }
        cout<<result<<endl;
        result=0;
    }

    return 0;
}

100分：

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


int main (){
    
    int n, m, k;
    cin >> n >> m >> k;
    int l, r;
    vector<int> v(200010);
    for (int i = 0; i < n; i++) {
    
        cin >> l >> r;
        int tl = max(0, l - r - k + 1);
        int tr = max(0, l - k);
        v[tl]++;
        v[tr + 1]--;
    }
    for (int i = 1; i < 200010; i++) {
    
        v[i] += v[i - 1];
    }
    for (int i = 0; i < m; i++) {
    
        cin >> l;
        cout << v[l] << endl;
    }

    return 0;

}

关于这题

第一次写的 虽然没超时 但是还是70分
后面看了别人的解法，发现可以换个思路，我们得到每个时间点做核酸可以进入场所的数目，就不需要两个for循环遍历了，这里用到了差分数组。

差分数组
差分数组是一个数据结构。相当于前缀和的逆运算。
差分数组的功能是修改区间，查询点。
修改区间的时间复杂度是O(1).
查询点的时间复杂度是O(n)。若配合树状数组时间复杂度可达到O(log n)。
（1）数组中元素的值全为0

原数组： 0 0 0 0 0 0
下标： 0 1 2 3 4 5
现在要把下标为2-4之间的数加5

修改区间：
差分数组： 0 0 5 0 0 -5
下标： 0 1 2 3 4 5

结果：
结果数组： 0 0 5 5 5 0
下标： 0 1 2 3 4 5

修改区间：下标为x-y之间的数加n
把下标为x的数加n，下标为y的数减n
得到修改后的结果数组：结果数组第一个数和差分数组第一个数一样，后面结果数组的每个数等于差分数组的当前数减去差分数组前一个数。

（2）其他情况

原数组： 4 7 9 6 5 2
下标： 0 1 2 3 4 5
现在要把下标为1-2之间的数加3

先得到差分数组：
差分数组： 4 3 2 -3 -1 -3
下标： 0 1 2 3 4 5

修改区间：
差分数组： 4 6 2 -6 -1 -3
下标： 0 1 2 3 4 5

结果：
结果数组： 4 10 12 6 5 2
下标： 0 1 2 3 4 5

得到差分数组：第一个数和原数组一致，后面的每个数等于原数组当前数减去原数组当前数的前面一个数
修改区间：下标为x-y之间的数加n
把下标为x的数加n，下标为y的数减n
得到修改后的结果数组：结果数组第一个数和差分数组第一个数一样，后面结果数组的每个数等于差分数组的当前数减去差分数组当前数的前一个数。