CCF CSP 201809-2.买菜

问题描述

　　小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段$[a_1,b_1],[a_2,b_2]…[a_n,b_n]$在装车，对于小W来说有n个不相交的时间段$[c_1,d_1],[c_2,d_2]…[c_n,d_n]$在装车。其中，一个时间段[s, t]表示的是从时刻s到时刻t这段时间，时长为t-s。
　　由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。

输入格式

　　输入的第一行包含一个正整数n，表示时间段的数量。
　　接下来n行每行两个数$a_i，b_i$，描述小H的各个装车的时间段。
　　接下来n行每行两个数$c_i，d_i$，描述小W的各个装车的时间段。

输出格式

　　输出一行，一个正整数，表示两人可以聊多长时间。

样例输入

4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14

样例输出

数据规模和约定

　　对于所有的评测用例，1 ≤ n ≤ 2000, $a_i < b_i < a_{i+1}，c_i < d_i < c_{i+1}$,对于所有的i(1 ≤ i ≤ n)有，1 ≤ $a_i, b_i, c_i, d_i$ ≤ 1000000。

分析：

暴力法：双重循环

用time表示小H和小W能够聊天的时间。

用二维数组hArr存储小H装车的n个时间段，二维数组wArr存储小W装车的n个时间段。

遍历数组hArr，循环内部再遍历数组wArr，

令x为当前的两个时间段中最大的下界，y为最小的上界，即

x = max(hArr[i][0], wArr[j][0])，y= min(hArr[i][1], wArr[j][1])

若y - x > 0，则表示两个时间段有交叉，time += y - x。

#include <cstdio>
#include <algorithm>
using namespace std;

void input(int arr[][2], int n) {
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &arr[i][0], &arr[i][1]);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	int hArr[n][2], wArr[n][2];
	input(hArr, n);
	input(wArr, n);

	int time = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x = max(hArr[i][0], wArr[j][0]);
			int y = min(hArr[i][1], wArr[j][1]);
			if (y - x > 0) {
				time += y - x;
			}
		}

	}

	printf("%d\n", time);
	return 0;
}