Home > Old Blog Posts > USACO 1.2.1 Milking Cows

USACO 1.2.1 Milking Cows


这道题的标准做法是离散化或线段树,但放在Chapter 1显然就是让人模拟的。

直接按区间存储就可以了,用一个数组来存放每个时刻的状态。

存储时注意:

若数据为700~1000,那么你存储的应该是a[700]~a[999]!

代码:

/*
ID: dementr1
PROG: milk2
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
bool k[10000001];
int main()
{
ifstream fin(“milk2.in”);
ofstream fout(“milk2.out”);
int n,i,j,a,b,now1,now2,max1,max2,uptime=-1,lowtime=9999999;
fin>>n;
for(i=0;i<n;i++)
{
fin>>a>>b;
if(b>uptime) uptime=b;
if(lowtime>a) lowtime=a;
for(j=a;j<b;j++) k[j]=true;
}
max1=max2=0;
if(k[0]) now1=1;
else now1=0;
if(k[0]) now2=0;
else now2=1;
for(i=lowtime;i<=uptime;i++)
{
if(k[i]&&k[i-1])
{
now1++;
}
else if(k[i])
{
now1=1;
}
else now1=0;if(now1>max1) max1=now1;
if(i!=uptime)
{
if((!k[i])&&(!k[i-1]))
{
now2++;
}
else if(!k[i])
{
now2=1;
}
else now2=0;
if(now2>max2) max2=now2;
}
}
fout<<max1<<” “<<max2<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: