题目描述

blablabla

样例

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2005;

#define x first
#define y second

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    pair<int, int> W[N];
    pair<int, int>H[N];
    for (int i = 0; i < n; i++)
        cin >> W[i].x >> W[i].y;
    for (int i = 0; i < n; i++)
        cin >> H[i].x >> H[i].y;

    int ans = 0;
    int i = 0, j = 0;                                   //利用双指针,判断区间有没有重叠
    while (j < n && i < n) {
        if (W[i].x > H[j].y) {
            j++;
            continue;
        }
        else if (W[i].y <= H[j].x) {
            i++;
        }
        else {
            int a = max(W[i].x, H[j].x);
            int b = min(W[i].y, H[j].y);
            ans += b - a;
            if (W[i].y >= H[j].y)
                j++;
            else if (W[i].y < H[j].y)
                i++;
        }
    }
    cout << ans << endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla