usaco 1.2 Milking Cows（类hash表）

本文主要是介绍usaco 1.2 Milking Cows（类hash表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时！！

第一种思路：我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较

1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end )

2 反之 这个区间结束 ans1=max(ans1,tem_end-tem_begin) ，ans2=max(ans2,beg[i]-tem_end)  保存这个区间的答案 并重新给下一个区间戴上开头tem_begin=beg[i]，tem_end=ed[i]。直至遍历结束。

目测时间复杂度是快排加遍历就是O（nlogn+n) 不知道为什么会超时 求同学指导。

附上 milk2  TLE  的代码

/*
ID: who jay
LANG: C++
TASK: milk2
*/#include<stdio.h>int max(int a,int b)
{return a>b?a:b;
}void swap(int &a,int &b)
{a=a+b-(b=a);
}void qsort(int A[],int B[],int left,int right)
{int flag=A[left+(right-left)/2];int l=left,r=right;while(A[l]<flag) l++;while(A[r]>flag) r--;if(l<=r){swap(B[l],B[r]);swap(A[l++],A[r--]);}if(l<right) qsort(A,B,l,right);if(left<r) qsort(A,B,left,r);
}int main()
{FILE *fin  = fopen ("milk2.in", "r");FILE *fout = fopen ("milk2.out", "w");int n,i,beg[5000],ed[5000],tem_begin,tem_end;int ans1,ans2;fscanf(fin,"%d",&n);for(i=0; i<n; i++)fscanf(fin,"%d %d",&beg[i],&ed[i]);qsort(beg,ed,0,n-1);tem_begin=beg[0];tem_end=ed[0];ans1=tem_end-tem_begin;ans2=0;for(i=1; i<n; i++){if(beg[i]<=tem_end){tem_end=max(ed[i],tem_end);continue;}else{ans1=max(ans1,tem_end-tem_begin);ans2=max(ans2,beg[i]-tem_end);tem_begin=beg[i];tem_end=ed[i];}}fprintf(fout,"%d %d\n",ans1,ans2);return 0;
}

经过1.3 Mixing milk 的结构体排序的qsort（）研究以后 不超时代码：

/*
ID: who jay
LANG: C++
TASK: milk2
*/#include<stdio.h>
#include<algorithm>
using namespace std;struct Milking
{int beg;int ed;
}milk[5000];int milkcmp(const void *va,const void *vb)
{Milking *a,*b;a= (Milking*)va;b= (Milking*)vb;if(a->beg > b->beg)return 1;if(a->beg < b->beg)return -1;return 0;
}int main()
{FILE *fin  = fopen ("milk2.in", "r");FILE *fout = fopen ("milk2.out", "w");int n,i,tem_begin,tem_end;int ans1,ans2;fscanf(fin,"%d",&n);for(i=0; i<n; i++)fscanf(fin,"%d %d",&milk[i].beg,&milk[i].ed);qsort(milk,n,sizeof(Milking),milkcmp);tem_begin=milk[0].beg;tem_end=milk[0].ed;ans1=tem_end-tem_begin;ans2=0;for(i=1; i<n; i++){if(milk[i].beg<=tem_end){tem_end=max(milk[i].ed,tem_end);continue;}else{ans1=max(ans1,tem_end-tem_begin);ans2=max(ans2,milk[i].beg-tem_end);tem_begin=milk[i].beg;tem_end=milk[i].ed;}}fprintf(fout,"%d %d\n",ans1,ans2);return 0;
}

第二种思路 看完第一种思路再看第二种 你会有种被这题深深伤害的赶脚

第二种思路：

1 先将0到1000000时间段赋值为0，表示这段时间没人挤牛奶

2 将输入时间段的点标记为1，表示这段时间有人挤牛奶，并找出有人挤牛奶的最小时间min，最大时间max

3 在最小时间与最大时间之间遍历，

    若 a[i]==1 && a[i+1]==1 表明此刻有人挤牛奶 tempt1++

    若 a[i]==1 && a[i+1]==0 表明下一刻将没有人挤牛奶 temp1++ 并比较temp1与ans1的大小 并令下一段temp1=0

    若 a[i]==0 && a[i+1]==0 表明此刻没有人挤牛奶 temp2++

    若 a[i]==0 && a[i+1]==1 表明下一刻将有人挤牛奶 temp2++ 并比较temp2与ans2的大小 并令下一段temp2=0

4 ko！！！！

这种思路好在 不用排序和区间重合段都被1覆盖 不用再区别

附上代码~

/*
ID: who jay
LANG: C++
TASK: milk2
*/
#include<stdio.h>int main()
{FILE *fin  = fopen ("milk2.in", "r");FILE *fout = fopen ("milk2.out", "w");int i,n,temp1,temp2,start,end,ans1,ans2,min,max;while(fscanf(fin,"%d",&n)!=EOF){temp1=0;temp2=0;ans1=0;ans2=0;min=1000000;max=0;bool a[1000001]={0};while(n--){fscanf(fin,"%d %d",&start,&end);if(min>start)min=start;if(max<end)max=end;for(i=start; i<end; i++)a[i]=1;}for(i=min; i<max; i++){if(a[i]==1 && a[i+1]==1){temp1++;continue;}if(a[i]==1 && a[i+1]==0){temp1++;if(temp1>ans1)ans1=temp1;temp1=0;}if(a[i]==0 && a[i+1]==0){temp2++;continue;}if(a[i]==0 && a[i+1]==1){temp2++;if(temp2>ans2)ans2=temp2;temp2=0;}}fprintf(fout,"%d %d\n",ans1,ans2);}return 0;
}

这篇关于usaco 1.2 Milking Cows（类hash表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---