Let's Chat ZOJ - 3961

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3961

解题思路：分别用两个结构体数组存A B两个人发送消息的区间。因为不存在一个人会有区间重复的情况，例如先给一个1 5再给一个4 6，不会存在这样的情况。那么我们只需要将两个人的聊天区间排序一下，然后不断的比较两个人的聊天区间就行，有重复的且大于等于m就会有积分增加。

code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

struct node{
	int l, r;
};
node a[107];
node b[107];

bool cmp(node n1, node n2)
{
	return n1.l < n2.l;
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n, m, x, y;
		scanf("%d %d %d %d", &n, &m, &x, &y);
		for(int i=0; i<x; i++)
			scanf("%d %d", &a[i].l, &a[i].r);
		for(int i=0; i<y; i++)
			scanf("%d %d", &b[i].l, &b[i].r);
		sort(a, a+x, cmp);
		sort(b, b+y, cmp);
		int i = 0, j = 0;
		ll ans = 0;
		while(i < x && j < y)
		{
			if(a[i].r - a[i].l < m-1)	// a的这个区间长度小于m 
			{
				i++;
				continue;
			}
			else if(b[j].r - b[j].l < m-1)	// b的这个区间长度小于m 
			{
				j ++;
				continue;
			}
			else if(a[i].r <= b[j].l)	// a完全在b的左边 
				i++;
			else if(a[i].l >= b[j].r)	// a完全在b的右边 
				j++;
			else
			{
				// a和b的位置的有重复部分的四种情况 
				if(a[i].l <= b[j].l && a[i].r >= b[j].r)
				{
					ans += b[j].r - b[j].l + 2 - m;
					j++;
				}
				else if(a[i].l <= b[j].l && a[i].r <= b[j].r)
				{
					if(a[i].r - b[j].l >= m-1)
						ans += a[i].r - b[j].l + 2 - m;
					i++;
				}
				else if(a[i].l >= b[j].l && a[i].r >= b[j].r)
				{
					if(b[j].r - a[i].l >= m-1)
						ans += b[j].r - a[i].l + 2 - m;
					j++;
				}
				else if(a[i].l >= b[j].l && a[i].r <= b[j].r)
				{
					if(a[i].r - a[i].l >= m-1)
						ans += a[i].r - a[i].l + 2 - m;
					i++;
				}
			}
		}
		printf("%d\n", ans);
	}
	
	
	
	
	return 0;
}