CCF201809-2 买菜

其实这个题有简单的方法,用空间换时间。我试过那种方法,当时ZZ了,用的i=a;i<=b;i++,最后统计数组中值为2的数。然后长度总是会超,现在想,当时就是白痴。(正确的应该是i=a;i<b;i++。应该左闭右开)

 

不过后来换了一种方法,也可以做,即:定义一个判断是否有交叉的函数,然后进行暴力破解,若区间有相交,则进行相交区域计算(中间需要剪枝。)

 

下面贴出代码:

#include<iostream>
#include<algorithm>

using namespace std;

struct key{
	int x;
	int y;
};

bool cha(key a,key b)//交叉区域判断
{
	if (a.x>b.x)
	{
		key t;
		t=a;
		a=b;
		b=t;
	}
	if(a.y<=b.x)
	{
		return false;
	}
	else 
	{
		return true;
	}
	
}
int main()
{
	int n;
	cin>>n;
	key h[2001];
	key w[2001];
	for(int i=0;i<n;i++)
	{
		cin>>h[i].x>>h[i].y;
	}
	for(int i=0;i<n;i++)
	{
		cin>>w[i].x>>w[i].y;
	}
	int temp=0;
	int all=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(cha(h[i],w[j]))
			{
				temp=h[i].y-h[i].x+w[j].y-w[j].x-(max(h[i].y,w[j].y)-min(h[i].x,w[j].x));
				all+=temp;

			}
			if(w[j].x>h[i].y)//剪枝
			{
				break;
			}
			
		}
	}
	cout<<all;
	return 0;
	
	
 } 

 

    原文作者:奈何辰星无可奈
    原文地址: https://blog.csdn.net/qq_38346791/article/details/88344597
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞