首页 > 代码库 > USACAO Milking Cows 线段树

USACAO Milking Cows 线段树

背景:我是用最低效率的暴力模拟过的,竟然建了个1000000的数组,论文说只要计算量不超过2000000即可以过。

学习:1.对于我这种方法可以改进,那就是对于数据的开头和结尾都拉通来排序,让后用1代替最小的,2代替第二小的,3代替........然后把1,2,3,4,5......来进行模拟操作最后再还原回去求区间长度,这样就提高了很多效率。但模拟也不是最好效率,这时就要对已经抽象了的1,2,3.,4......用线段树了(插入:http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html     (线段树在ACM中的知识))

2.可以考虑按左边界排序后进行区间合并操作(这样合并的时候比较容易判断)

心得:引用上周培训课学长讲的一句话:很多数据我们对他排序后会发现惊喜!!

我的暴力代码:

/*
ID:jibancan1
LANG:C++
TASK:milk2
*/
#include<stdio.h>
#define maxline 1000000
int str[maxline];
int main(void)
{  
    freopen("milk2.in","r",stdin);
	freopen("milk2.out","w",stdout); 
	int n,min=maxline,max=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int start,end;
		scanf("%d %d",&start,&end);
		for(int j=start;j<end;j++)
		    str[j]++;
		if(start<min) min=start;
		if(end>max) max=end;    
	}
	int cout0=0,cout1=1,an0=0,an1=0;//0 mean no one is milking ,1 means the oppose.
	for(int k=min;k<max;k++)//find the longst no and yes milking interval.
	{
		if(str[k+1]>0)
		{
		   if(cout0>an0) an0=cout0;
		   cout0=0;
		   cout1++;
		} 
		else
		{
			if(cout1>an1) an1=cout1;
			cout1=0;
			cout0++;	
		}
	}
	printf("%d %d\n",an1,an0);
	return 0; 
}   


USACAO Milking Cows 线段树