试题编号： 201809-2
试题名称： 买菜
时间限制： 1.0s
内存限制： 256.0MB
问题描述
小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。
思路：
画出两条时间线，不难看出，我们需要得到的解是由两个时间段相交所得出的，那么就存在三种情况：
- 两个相邻时间段互斥，即没有相交时间段
- 大的时间段包含了小的，甚至可能包含多个时间段
- 两个时间段相交，但各不包含于彼此，如下图的例子
再将逻辑简化，就会发现只要以一条时间线为基准，遍历另外一条时间线上的时间段，算出与它相交的时间块的总和，即为最后答案。
核心代码如下：
for(int i = 0 ; i <= n-1 ; i++)
{
for(int j = 0 ; j <= n-1 ; j++)
{
//如果他们之间有相交的时间，则sum += 该时间
if ((min1(h[i].r , w[j].r) - max(h[i].l , w[j].l))>0){
sum = sum + min1(h[i].r , w[j].r) - max(h[i].l , w[j].l) ;
}
}
}
补充：
上述代码还可以进行优化，例如：当选定的那条时间线上的一个时间块遍历另一条时间线结束后，到了下一个时间块，遍历其实就可以略过另一条线上右边比选定线的上一个时间块左边还要小的时间块。
完整代码及其注释如下：
#include <bits/stdc++.h>
using namespace std;
struct Node
{ // 结构体，从左到右，代表何时开始何时结束
int l;
int r;
};
//求更小者
int min1(int a , int b){
return a<=b?a:b;
}
//求更大者
int max1(int a , int b){
return a>=b?a:b;
}
int main(int argc, char const *argv[])
{
int n; //买n次菜
int sum = 0 ; //用来记录求得的时间
cin>>n; //输入n
struct Node h[n],w[n]; //两个结构体数组h,w 代表小H,小W
//输入小H的装车时间段
for(int i = 0 ; i <= n-1 ; i++)
scanf("%d %d",&h[i].l,&h[i].r);
//输入小W的装车时间段
for(int i = 0 ; i <= n-1 ; i++)
scanf("%d %d",&w[i].l,&w[i].r);
for(int i = 0 ; i <= n-1 ; i++)
{
for(int j = 0 ; j <= n-1 ; j++)
{
//如果他们之间有相交的时间，则sum += 该时间
if ((min1(h[i].r , w[j].r) - max(h[i].l , w[j].l))>0){
sum = sum + min1(h[i].r , w[j].r) - max(h[i].l , w[j].l) ;
}
}
}
printf("%d",sum);
return 0;
}
