Description

三個農(nóng)民每天清晨5點(diǎn)起床，然后去牛棚給3頭牛擠奶。第一個農(nóng)民在300時刻(從5點(diǎn)開始計(jì)時，秒為單位)給他的牛擠奶，一直到1000時刻。第二個農(nóng)民在700時刻開始，在 1200時刻結(jié)束。第三個農(nóng)民在1500時刻開始2100時刻結(jié)束。期間最長的至少有一個農(nóng)民在擠奶的連續(xù)時間為900秒(從300時刻到1200時刻)，而最長的無人擠奶的連續(xù)時間(從擠奶開始一直到擠奶結(jié)束)為300秒(從1200時刻到1500時刻)。
　　你的任務(wù)是編一個程序，讀入一個有N個農(nóng)民(1 <= N <= 5000)擠N頭牛的工作時間列表，計(jì)算以下兩點(diǎn)(均以秒為單位):
? 最長至少有一人在擠奶的時間段。
? 最長的無人擠奶的時間段。

Input

Line 1: 一個整數(shù)N。
Lines 2…N+1: 每行兩個小于1000000的非負(fù)整數(shù)，表示一個農(nóng)民的開始時刻與結(jié)束時刻。

Output

一行，兩個整數(shù)，即題目所要求的兩個答案。

Sample Input
3
300 1000
700 1200
1500 2100

Sample Output
900 300
.
.
.
.
.
.
分析
離散化(我打的真的是離散嗎？)
每一段時間都可以看成一條線段
將開頭和結(jié)尾映射到數(shù)軸上
在數(shù)軸上從左到右掃描
對于一個點(diǎn)，如果它在某一條線段上，則累加
(注意，對于時間的間隔，它只可能存在于兩點(diǎn)之間)
.
.
.
.
.
程序：(代碼丑陋，請別介意)

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,x1[6000],y1[6000],x[10001];int main() {scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d%d",&x1[i],&y1[i]);x[i*2-1]=x1[i];x[i*2]=y1[i];}sort(x+1,x+2*n+1);long long ans1=0,ans2=0,fa1=0,fa2=0;for (int i=2;i<=2*n;i++){int bz=0;for (int j=1;j<=n;j++)if (x[i]<=y1[j]&&x[i-1]>=x1[j]){bz=1;fa1+=x[i]-x[i-1];break;}if (bz==1&&fa1>ans1) ans1=fa1;if (bz==0){fa1=0;fa2=x[i]-x[i-1];if (fa2>ans2) ans2=fa2;}}cout<<ans1<<' '<<ans2;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10292812.html

總結(jié)

以上是生活随笔為你收集整理的USACO 1.2 挤牛奶的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。