USACO chapter 1 section 1.2 Milking Cows

USER: tianbing tianbing [tbbd4261]
TASK: milk2
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 2968 KB]
   Test 2: TEST OK [0.000 secs, 2968 KB]
   Test 3: TEST OK [0.011 secs, 2968 KB]
   Test 4: TEST OK [0.022 secs, 2968 KB]
   Test 5: TEST OK [0.011 secs, 2968 KB]
   Test 6: TEST OK [0.011 secs, 2968 KB]
   Test 7: TEST OK [0.011 secs, 2968 KB]
   Test 8: TEST OK [0.000 secs, 2968 KB]

All tests OK.

Your program ('milk2') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!

刚开始以结束时间排序,WA了一次,后来想想要以开始时间排序才是正确的
1,用s 和 e分别纪录一段时间的开始和结束,分别是最大和最小的值
如果两段时间为1  3 ,2  6的话,则s=1,e=6 不断更新,纪录e - s的最大值即可
2, 间隔嘛直接拿当前的开始时间和前面连续的最大结束时间e比较即可,同样纪录最大的

改代码有点问题,修正在下面。

 1/*
 2ID:tbbd4261
 3LANG:C++
 4PROG:milk2
 5*/

 6#include<iostream>
 7#include<fstream>
 8#include<algorithm>
 9using namespace std;
10 struct milk
11{
12 int start;
13 int end;
14}
a[5005]; 
15
16bool f(struct milk a,struct milk b)
17{
18     return a.start<b.start;
19}

20int main()
21{
22    ifstream cin("milk2.in");
23    ofstream cout("milk2.out");
24    int n,i,s,e,maxm=0,maxt=0;
25    cin>>n;
26    for(i=1; i<=n; i++)
27    cin>>a[i].start>>a[i].end;
28    sort(a+1,a+1+n,f);
29    s=a[1].start; e=a[1].end;
30    for(i=1;i<=n;i++)
31    {
32      if(a[i].start>e)
33      {
34        if(a[i].start-> maxt)maxt=a[i].start-e;
35        s=a[i].start; e=a[i].end;
36      }

37      else {
38           if(a[i].end>e) e=a[i].end; 
39           if(e->maxm)maxm=e-s; 
40           }

41    }

42    cout<<maxm<<' '<<maxt<<endl;
43    //system("pause");
44    
45    return 0;
46}

 KK朋友指出错误后修正:
#include<iostream>
#include
<fstream>
#include
<algorithm>
using namespace std;
struct milk
{
 
int start;
 
int end;
}a[
5005]; 

bool f(struct milk a,struct milk b)
{
     
return a.start<b.start;
}
int main()
{
    
//ifstream cin("milk2.in");
    
//ofstream cout("milk2.out");
    int n,i,s,e,maxm=0,maxt=0;
    cin
>>n;
    
for(i=1; i<=n; i++)
    cin
>>a[i].start>>a[i].end;
    sort(a
+1,a+1+n,f);
    s
=a[1].start; e=a[1].end;
    
for(i=1;i<=n;i++)
    {
      
if(a[i].start>e)
      {
        
if(a[i].start-> maxt)maxt=a[i].start-e;
        s
=a[i].start; e=a[i].end;
        
if(e-s>maxm)maxm=e-s; //这时候没有检查是否比maxm更大。修改的地方。
      }
      
else {
           
if(a[i].end>e) e=a[i].end; 
           
if(e->maxm)maxm=e-s; 
           }
    }
    cout
<<maxm<<' '<<maxt<<endl;
    system(
"pause");
    
    
return 0;
}

posted on 2010-05-18 22:00 田兵 阅读(1363) 评论(2)  编辑 收藏 引用 所属分类: USACO

评论

# re: USACO chapter 1 section 1.2 Milking Cows[未登录] 2010-08-21 15:50 kk

如果input改成
4
100 200
201 302
303 402
403 503

你的code跑出來是錯得
  回复  更多评论   

# re: USACO chapter 1 section 1.2 Milking Cows 2010-08-21 19:01 田兵

@kk

谢谢哥们指出错误。
对于你的那组数据应该输出
101 1
已修改。   回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜