CCF 201809-2 买菜

快来打我* 2023-07-18 02:24 14阅读 0赞

> 问题描述  
> 　　小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段\[a1,b1\],\[a2,b2\]…\[an,bn\]在装车，对于小W来说有n个不相交的时间段\[c1,d1\],\[c2,d2\]…\[cn,dn\]在装车。其中，一个时间段\[s, t\]表示的是从时刻s到时刻t这段时间，时长为t-s。  
> 　　由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。  
> 输入格式  
> 　　输入的第一行包含一个正整数n，表示时间段的数量。  
> 　　接下来n行每行两个数ai，bi，描述小H的各个装车的时间段。  
> 　　接下来n行每行两个数ci，di，描述小W的各个装车的时间段。  
> 输出格式  
> 　　输出一行，一个正整数，表示两人可以聊多长时间。  
> 样例输入  
> 4  
> 1 3  
> 5 6  
> 9 13  
> 14 15  
> 2 4  
> 5 7  
> 10 11  
> 13 14  
> 样例输出  
> 3  
> 数据规模和约定  
> 　　对于所有的评测用例，1 ≤ n ≤ 2000, ai < bi < ai+1，ci < di < ci+1,对于所有的i(1 ≤ i ≤ n)有，1 ≤ ai, bi, ci, di ≤ 1000000。

//
    // Created by asimov on 2020/3/23.
    //
    
    #ifndef CSP_201809_2_H
    #define CSP_201809_2_H
    
    #endif //CSP_201809_2_H
    
    #include "bits/stdc++.h"
    
    using namespace std;
    typedef long int li;
    int n;
    
    vector<pair<li, li> > H, W;
    li a, b, c, d;
    li chatTime = 0;
    
    int fun() {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            pair<li, li> tempH;
            tempH.first = a;
            tempH.second = b;
            H.push_back(tempH);
        }
    
        for (int i = 0; i < n; i++) {
            cin >> c >> d;
            pair<li, li> tempW;
            tempW.first = c;
            tempW.second = d;
            W.push_back(tempW);
        }
    
    
        for (int i = 0; i < H.size(); i++) {
            a = H[i].first;
            b = H[i].second;
            for (int j = 0; j < W.size(); j++) {
                c = W[j].first;
                d = W[j].second;
    //区间位置的7种情况A[a,b]  B[c,d]
                if (b <= c)
                    continue;//不相交
                else if (a > c && b < d) {
                    chatTime += b - a;//B包含A
                } else if (c > a && d < b) {
                    chatTime += d - c;//A包含B
                } else if (a < c && c < d && d > b) {
                    chatTime += b - c;//A和B的左半部分重叠
                } else if (a < d && d < b && c < a) {
                    chatTime += d - a;//A和B的有半部分重叠
                } else if (a == c) {
                    //头相等
                    chatTime += min(b, d) - a;
                } else if (b == d) {
                    //尾相等
                    chatTime += b - max(a, c);
                } else
                    continue;
            }
        }
        cout << chatTime;
        return 0;
    }
    /*
    4
    1 3
    5 6
    9 13
    14 15
    2 4
    5 7
    10 11
    13 14
     */