`

【区间覆盖】USACO Milking Cows

阅读更多

KIDx的解题报告

 

进入USACO要注册才能看题: http://train.usaco.org/usacogate

题目:【翻译版、是别处的网站】http://www.wzoi.org/usaco/12%5C211.asp

SAMPLE INPUT (file milk2.in)
3
300 1000
700 1200
1500 2100
SAMPLE OUTPUT (file milk2.out)
900 300

/*
ID: 1006100071
LANG: C++
TASK: milk2
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define M 5005

struct times{
	int a, b;    //a区间开端,b区间末端
}x[M];

int end[M];

bool cmp (times x, times y)
{
	if (x.a == y.a)
		return x.b < y.b;
	return x.a < y.a;
}

int main()
{
	/*freopen ("milk2.in", "r", stdin);
	freopen ("milk2.out", "w", stdout);*/
	int n, i, start, maxs, maxs2;
	scanf ("%d", &n);
	for (i = 0; i < n; i++)
		scanf ("%d%d", &x[i].a, &x[i].b);
	sort (x, x+n, cmp);
	//end[i]--------------------储存前i个【包括i】区间的最大末端
	end[0] = x[0].b;
	for (i = 1; i < n; i++)
	{
		if (x[i].b > end[i-1])
			end[i] = x[i].b;
		else end[i] = end[i-1];
	}
	//求最大连续覆盖长度
	start = maxs = 0;
	for (i = 0; i < n; i++)
	{
		if (i+1 < n && x[i+1].a <= end[i])
			continue;
		else
		{
			int tp = end[i] - x[start].a;
			if (tp > maxs) maxs = tp;
			start = i + 1;
		}
	}
	//求最大区间间隔【间隔是空白区域】 
	maxs2 = 0;
	for (i = 1; i < n; i++)
		if (x[i].a > end[i-1] && maxs2 < x[i].a - end[i-1])
			maxs2 = x[i].a - end[i-1];
	printf ("%d %d\n", maxs, maxs2);
	return 0;
}

 

2
0
分享到:
评论

相关推荐

    USACO题目Milking Cows及代码解析

    ### USACO 题目解析:Milking Cows #### 题目背景与要求 本题目来源于美国计算机奥林匹克竞赛(USACO),题目名为“Milking Cows”。题目描述了一个有趣的场景:三位农民每天早上给三头牛挤奶,并给出了各自的挤奶...

    USACO官网93题fps格式 OJ题库

    6 [1.2] 挤牛奶Milking Cows 7 [1.2] 方块转换 Transformations 8 [1.2] 回文平方数 Palindromic Squares 9 [1.2] 双重回文数 Dual Palindromes 10 [1.3] 混合牛奶 Mixing Milk 11 [1.3] 修理牛棚 Barn Repair 12 ...

    USACO总结

    随着难度的提升,本章开始引入更复杂的问题,例如“Milking Cows”,这道题目的解决策略需要运用到贪心算法。此外,“Transformations”、“Name That Number”等题目进一步加深了对模拟算法的理解。 ### 四、...

    USACO英汉对照题目

    1.2.1 "Milking Cows" 可能与数组和排序有关,可能是优化挤牛奶的效率问题。 1.2.3 "Name That Number" 可能是关于数字表示和逻辑推理的问题。 1.2.4 "Palindromic Squares" 和 "Dual Palindromes" 强调了对回文数的...

    USACO所有题目题解

    5. **Milking Cows (milk2)**: 本题涉及时间调度,有三种主要思路。第一种是离散化,通过排序并遍历,复杂度为O(nlogn+n)。第二种思路是在保持字符串不变的情况下,每次将首位移至末尾,从而从两头同时搜索。第三种...

    USACO题解(NOCOW整理版).doc

    Chapter 1 Section 1.2 Milking Cows (milk2) 这道题有三种思想。第一种思想是离散化(其实就是进行了优化的搜索而已),按照开始时间升序排序,然后从左到右扫一遍,复杂度是 O(nlogn+n) 的(排序+扫一遍,用堆、...

    USACO全部译题

    **1.2.1 Milking Cows** - **问题描述**:此题要求计算奶牛挤奶的最优方案,以达到最大化的产出。 - **算法思想**:可以使用贪心策略来解决问题,例如按照预期产出的降序来安排奶牛的挤奶顺序。 **1.2.2 ...

    usaco题目的副本1

    8. **算法优化**:在"Milking Cows"和"Transformations"题目中,优化算法的关键在于减少对已有列表的直接修改,而是创建新列表来存储结果,这样可以使程序执行过程更简单,也更易于理解。 通过理解和应用这些知识点...

    USACO(Train)解题报告.doc

    ### Chapter 1 Section 1.2 - Milking Cows (milk2) 本题提出了三种解题思路。一种是离散化,通过对开始时间进行排序,然后遍历整个序列,复杂度为O(nlogn+n)。这种方法的关键是维护一个当前区间`[tmp_begin, tmp_...

    USACO全部题目

    #### Milking Cows 这道题考察了学生对动态规划的理解和应用能力。题目背景通常是关于如何最大化奶牛产奶量的问题,可以通过构建状态转移方程来求解最优解。动态规划的核心思想是将一个复杂问题分解成一系列更小的...

    USACO月赛题解1

    【USACO月赛题解1】中的知识点涵盖了多种算法和问题解决策略,适用于计算机科学,尤其是算法竞赛。以下是对各个题目及其所涉及算法的详细解释: 1. **Fiber Communications** - 这是一个并查集(Disjoint Set Union...

    第1章总结1

    接着,1.2节重点是完整搜索,如"Milking Cows"中运用离散化技术,"Transformations"和"Name That Number"通过枚举解决,而"Palindromic Squares"和"Dual Palindromes"进一步强化了枚举法的应用。 1.3节围绕贪心算法...

Global site tag (gtag.js) - Google Analytics