201809-2买菜

题目

题目链接:买菜

image-20211203211821115

思路:前缀和

看到题目,第一想法就是前缀和,为什么?因为他要求两人装车的时间重叠的那一部分,然后我们用差分数组对他们装车的时间进行标记,然后两个标记重叠部分就是他们交流的时间。 但是,差分时要注意一点,我们差分处理的是一个时间点,而实际的时间是一个时间段,那我们怎么办呢?我们可以采用前闭后开的形式进行差分操作。比如,9点到10点这个时间段,我只对时间点9进行标记,代表一个9点到10点这一个小时。为什么不能右端点也闭合呢?因为如果你对右端点也进行标记的话,假如10点刚好是第一个人装车结束的时间,又是第二个人开始装车的时间,他们这时是不能交流的,但是你算进去了,所以会导致答案的错误。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 买菜 */
#include <iostream>
using namespace std;
const int N = 1e6 + 10;

int dif[N],arr[N], n;

void add(int l, int r) { dif[l]++, dif[r]--; }
int s, t;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        add(s,t);
    }
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        add(s,t);
    }
    for(int i=1;i<N;i++){
        arr[i]=dif[i]+arr[i-1];
    }
    int count=0;
    for(int i=1;i<N;i++){
        if(arr[i]==2)count++;
    }
    cout << count ;
    return 0;
}

不知道前缀和的小伙伴看这里

不知道前缀和是什么的朋友可以在下面这一篇博文中查看了解哦

{% post_link 算法基础/前缀和以及差分 前缀和以及差分%}

0%