CCF-CSP：201809-2买菜

CCF-CSP题目汇总

题目

试题编号： 201809-2
试题名称： 买菜
时间限制： 1.0s
内存限制： 256.0MB

问题描述

  小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

样例输出
3

数据规模和约定

  对于所有的评测用例，$1 \le n \le 2000, a_i < bi < a_i+1，c_i < d_i < c_i+1$,对于所有的$i(1 \le i \le n)$有，$1 \le a_i, b_i, c_i, d_i \le 1000000$。

解答

分析

  设定两个游标$i$,$j$,分别索引H和W的时间段，判断两个时间段有没有交集，如果有就计算交集的时长。然后移动先离开的那个人的游标。当一个人最后一个时间段走完，就结束程序。

代码

#include <iostream>

using namespace std;

int main() {

	int n;
	int H[2001][2];
	int W[2001][2];
	int time;
	time = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> H[i][0] >> H[i][1];
	}
	for (int i = 0; i < n; i++) {
		cin >> W[i][0] >> W[i][1];
	}

	int i, j;
	i = 0, j = 0;
	while (i < n&&j < n) {

		//判断两个时间段是否有交集
		if (H[i][1] > W[j][0] && H[i][0] < W[j][1]) {
			//我们以W为基准，判断H可能出现情况
			if (H[i][1] >= W[j][0] && H[i][0] <= W[j][0] && H[i][1] <= W[j][1]) {//H来 W来 H走 W走
				time += H[i][1] - W[j][0];
			}
			else if (H[i][0] >= W[j][0]  && H[i][1] <= W[j][1]) {//W来 H来 H走 W走
				time += H[i][1] - H[i][0];
			}
			else if (H[i][1] >= W[j][1] && H[i][0] >= W[j][0]) {//W来 H来 W走 H走
				time += W[j][1] - H[i][0];
			}
			else{//H来 W来 W走 H走
				time += W[j][1] - W[j][0];
			}
		}

		//更新先走的那个人
		if (H[i][1] < W[j][1]) {
			i++;
		}
		else{
			j++;
		}
	}

	cout << time;

	return 0;
}