Milking Cows(USACO)

/* ID:tianlin2 PROG:milk2 LANG:C++ */ #include <iostream> #include <fstream> using namespace std; int main() { ofstream fout("milk2.out"); ifstream fin("milk2.in"); int be1[5000],end1[5000]; //a为奶牛数,b为不挤奶的时间,c为最长不挤奶的时间,x为至少一个人挤奶的时间,y为最长挤奶时间 int a,b=0,c=0,x=0,y=0; fin>>a; for(int i=0;i!=a;++i) fin>>be1[i]>>end1[i]; //用一个数组做就可以了,//int *be1=new int[a]; //int *end1=new int[a]; /*for(int i=0;i!=a;++i) { be1[i]=be[i]; end1[i]=end[i]; }*/ //用数轴来考虑,分四种出现重复时间的情况,合并 for(int i=0;i!=a;++i) { for(int j=0;j!=a;++j) { if(end1[j]>=be1[i]&&end1[j]<=end1[i]&&be1[j]<=be1[i]) { be1[i]=be1[j]; end1[j]=end1[i]; } else if(be1[j]>=be1[i]&&end1[j]<=be1[i]) { be1[j]=be1[i]; end1[j]=end1[i]; } else if(be1[j]<=be1[i]&&end1[j]>=end1[i]) { be1[i]=be1[j]; end1[i]=end1[j]; } else if(be1[j]<=end1[i]&&be1[j]>=be1[i]&&end1[j]>=end1[i]) { be1[j]=be1[i]; end1[i]=end1[j]; } else continue; } } //以上处理完后仍然有,重复的,重复情况为第二种或者第三种 //算最大不挤奶时间错误的算法 /* for(int i=0;i!=a;++i) { b=0; int d=0; //MAX for(int j=0;j!=a;++j) { if(be1[i]>end1[j]) b=be1[i]-end1[j]; if(end1[i]<be1[j]) continue; if(be1[i]==be1[j]&&end1[i]==end1[j]) continue; if(d==0&&b!=0) d=b; //相当于D的初始化 if(b<d) d=b; if(b==8&&u==0&&d==8) { cout<<be1[i]<<' '<<end1[i]<<endl; cout<<be1[j]<<' '<<end1[j]<<endl; ++u; } } if(d>c) c=d; }*/ for(int i=0;i!=a;++i) { x=end1[i]-be1[i]; if(x>y) y=x; b=0; //d保存某个数轴段跟前一个数轴段的距离,若是此数轴段被包含在另一个数轴段里,则跳出循环 int d=0; //算最大不挤奶的时间时,就要考虑到重复的情况了 for(int j=0;j!=a;++j) { if(be1[i]==be1[j]&&end1[i]==end1[j]) continue; else if(end1[j]>=be1[i]&&end1[j]<=end1[i]&&be1[j]<=be1[i]) { d=0; break; } else if(be1[j]>=be1[i]&&end1[j]<=be1[i]) { d=0; break; } else if(be1[j]<=be1[i]&&end1[j]>=end1[i]) { d=0; break; } else if(be1[j]<=end1[i]&&be1[j]>=be1[i]&&end1[j]>=end1[i]) { d=0; break; } if(be1[i]>end1[j]) b=be1[i]-end1[j]; if(end1[i]<be1[j]) continue; if(d==0&&b!=0) d=b; //相当于D的初始化 if(b<d) d=b; } if(d>c) c=d; } fout<<y<<' '<<c<<endl; return 0; }

把时间看过一个数轴,然后合并重复的时间,但是没有排序,没有官方答案的简洁!

官方答案:

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define MAXMILKING 5000 //用结构体会比较方便,要学会用结构体 typedef struct Milking Milking; struct Milking { int begin; int end; }; Milking milking[MAXMILKING]; int nmilking; //qsort算法的函数,要学会用qsort算法,很方便的排序 int milkcmp(const void *va,const void *vb) { Milking *a,*b; a = (Milking*)va; b = (Milking*)vb; if(a->begin > b->begin) return 1; if(a->begin < b->begin) return -1; return 0; } void main(void) { FILE *fin,*fout; int i,j,t,tmilk,tnomilk; Milking cur; fin = fopen("milk2.in","r"); fout = fopen("milk2.out","w"); assert(fin != NULL && fout != NULL); /* read input,sort */ fscanf(fin,"%d",&nmilking); for(i=0; i<nmilking; i++) fscanf(fin,"%d %d",&milking[i].begin,&milking[i].end); qsort(milking,nmilking,sizeof(Milking),milkcmp); /* walk over list,looking for long periods of time */ /* tmilk = longest milking time */ /* tnomilk = longest non-milking time */ /* cur = current span of milking time being considered */ tmilk = 0; tnomilk = 0; cur = milking[0]; //一边计算,一边合并重复的时间,很值得学习 for(i=1; i<nmilking; i++) { if(milking[i].begin > cur.end) { /* a down time */ t = milking[i].begin - cur.end; if(t > tnomilk) tnomilk = t; t = cur.end - cur.begin; if(t > tmilk) tmilk = t; cur = milking[i]; } else { if(milking[i].end > cur.end) cur.end = milking[i].end; } } /* check final milking period */ t = cur.end - cur.begin; if(t > tmilk) tmilk = t; fprintf(fout,"%d %d/n",tnomilk); exit(0); }

排序算法很值得学习!

We read the list of times,sort it by start time,and then walk over the list once,merging overlapping times. Then we walk the list watching for long milking periods and long non-milking periods.

An alternate approach would be to just keep an array of size a million and mark off times. On a nice fast processor,that's probably fast enough,but our above algorithm will work even on slow processors,and it's not much harder to write.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!