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
/**//*
2
ID: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-e > 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-s >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-e > 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-s >maxm)maxm=e-s;
}
}
cout<<maxm<<' '<<maxt<<endl;
system("pause");
return 0;
}