[USACO1.2]挤牛奶Milking Cows

2024-01-29 20:32
文章标签 牛奶 cows usaco1.2 milking

本文主要是介绍[USACO1.2]挤牛奶Milking Cows,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

你的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段。

最长的无人挤奶的时间段。(从有人挤奶开始算起)

输入输出格式

输入格式:

Line 1:
一个整数N。
Lines 2..N+1:
每行两个小于1000000的非负整数,表示一个农民的开始时刻与结束时刻。

输出格式:
一行,两个整数,即题目所要求的两个答案。

输入输出样例

输入样例#1:
3
300 1000
700 1200
1500 2100
输出样例#1:
900 300

说明
题目翻译来自NOCOW。
USACO Training Section 1.2
.
.
.
.
.
.

分析

直接爆枚
设一个数组来记录当前的时间点十分有人挤牛奶
有则更新记录
注意:结束时间是没有挤牛奶的!!!
.
.
.
.
.
.

程序:
#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std;
int main()
{int n,b,e,max1,max2;b=1000005;e=-1;max1=0;max2=0;bool a[1000005];memset(a,false,sizeof(a));cin>>n;int x,y;for (int i=1;i<=n;i++){cin>>x>>y;if (x<b) b=x;if (y>e) e=y;for (int j=x;j<y;j++)a[j]=true;}int b1,e1;b1=0;e1=0;for (int i=b;i<e;i++)if (a[i]==true){b1++;if (e1>max2) max2=e1;e1=0;} elseif (a[i]==false){e1++;if (b1>max1) max1=b1;b1=0;}if (b1>max1) max1=b1;if (e1>max2) max2=e1;cout<<max1<<' '<<max2;return 0;
}

这篇关于[USACO1.2]挤牛奶Milking Cows的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/658101

相关文章

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

挤牛奶洛谷uasco

题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

2181:Jumping Cows

网址如下: OpenJudge - 2181:Jumping Cows (这是我拿去翻译的版本) 简单来说,题目要求我们求出一个子串,在奇数位的数加,偶数位的数减,求总的最大值 用贪心就可以做了 在波峰的时候加,波谷的时候减 代码如下: #include<cstdio>const int maxP = 150000;int P, val[maxP], ans;int

2015年2月2日 奶农倒牛奶的背后

郎教授说: 2014年12月份开始起,新疆山东山西河北北京都发现奶农倒奶的问题 中国人均的喝奶量是32.4公斤,只是世界平均的1/3 中国是市场是4000W吨,也就是哈有8000W吨的潜力 2007年,2011年,和2014年12月都出现倒奶事件 因为从这个时刻开始起,玉米等饲料价格上涨,原材料价格上涨导致农民只能杀牛倒奶 从2011年开始国际市场奶粉的价格比国内低

poj 2186 Popular Cows(tarjan + 强连通分量 + 缩点)

http://poj.org/problem?id=2186 题意:有n头牛,m个膜拜关系,膜拜关系是不可逆的而且是单向传递的,比如A膜拜B,B膜拜C,那么A也膜拜C,但B不一定膜拜A。最后问有多少头牛满足条件:除了它自己,其他所有的牛都膜拜它。 思路: 问题可以抽象为:给定一个有向图,n个顶点,m条有向边,有多少个顶点满足:其他所有的点都能到达该点。 首先假如图G是一个有向树

POJ 2186 Popular Cows (强连通分量)

题目地址:POJ 2186 先用强连通分量缩点,然后形成一棵树。我第一次用的判定条件是入度为分量数-1。虽然这种情况下确实正确。但是在树中也是有间接关系的。这个条件并不是充分必要条件。正确的做法是逆序建树,然后找根结点。而且根结点有且只有一个才可以。所以转化成了找出度为0的分量。 代码如下: #include <iostream>#include <string.h>#include

UVA10491 - Cows and Cars(概率)

UVA10491 - Cows and Cars(概率) 题目链接 题目大意:给你n个门后面藏着牛,m个门后面藏着车,然后再给你k个提示,在你作出选择后告诉你有多少个门后面是有牛的,现在问你作出决定后,根据提示改变你的选择能够成功的概率。 解题思路:简单的概率题,题目意思懂了应该没什么问题。 代码: #include <cstdio>#include <cstring>int

Bulls and Cows问题及解法

问题描述: You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide

POJ-2186 Popular Cows 强连通 + 缩点

http://poj.org/problem?id=2186 我们求强连通分量时,给每个顶点做一个标记,标记该顶点属于哪个强联通分量,然后属于同一个强连通分量的点就可以看作同一个点了。这就是所谓的“缩点”   此题用了个定理 :有向无环图(DAG)中,从任意一个点出发,必定可以到达某一个出度为0的点。   这个不用证明,直观想一下就行了。  因为无环,所以从一个点出发,必