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;
}
分享到:
相关推荐
### USACO 题目解析:Milking Cows #### 题目背景与要求 本题目来源于美国计算机奥林匹克竞赛(USACO),题目名为“Milking Cows”。题目描述了一个有趣的场景:三位农民每天早上给三头牛挤奶,并给出了各自的挤奶...
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 ...
随着难度的提升,本章开始引入更复杂的问题,例如“Milking Cows”,这道题目的解决策略需要运用到贪心算法。此外,“Transformations”、“Name That Number”等题目进一步加深了对模拟算法的理解。 ### 四、...
1.2.1 "Milking Cows" 可能与数组和排序有关,可能是优化挤牛奶的效率问题。 1.2.3 "Name That Number" 可能是关于数字表示和逻辑推理的问题。 1.2.4 "Palindromic Squares" 和 "Dual Palindromes" 强调了对回文数的...
5. **Milking Cows (milk2)**: 本题涉及时间调度,有三种主要思路。第一种是离散化,通过排序并遍历,复杂度为O(nlogn+n)。第二种思路是在保持字符串不变的情况下,每次将首位移至末尾,从而从两头同时搜索。第三种...
**1.2.1 Milking Cows** - **问题描述**:此题要求计算奶牛挤奶的最优方案,以达到最大化的产出。 - **算法思想**:可以使用贪心策略来解决问题,例如按照预期产出的降序来安排奶牛的挤奶顺序。 **1.2.2 ...
8. **算法优化**:在"Milking Cows"和"Transformations"题目中,优化算法的关键在于减少对已有列表的直接修改,而是创建新列表来存储结果,这样可以使程序执行过程更简单,也更易于理解。 通过理解和应用这些知识点...
### Chapter 1 Section 1.2 - Milking Cows (milk2) 本题提出了三种解题思路。一种是离散化,通过对开始时间进行排序,然后遍历整个序列,复杂度为O(nlogn+n)。这种方法的关键是维护一个当前区间`[tmp_begin, tmp_...
#### Milking Cows 这道题考察了学生对动态规划的理解和应用能力。题目背景通常是关于如何最大化奶牛产奶量的问题,可以通过构建状态转移方程来求解最优解。动态规划的核心思想是将一个复杂问题分解成一系列更小的...
【USACO月赛题解1】中的知识点涵盖了多种算法和问题解决策略,适用于计算机科学,尤其是算法竞赛。以下是对各个题目及其所涉及算法的详细解释: 1. **Fiber Communications** - 这是一个并查集(Disjoint Set Union...
接着,1.2节重点是完整搜索,如"Milking Cows"中运用离散化技术,"Transformations"和"Name That Number"通过枚举解决,而"Palindromic Squares"和"Dual Palindromes"进一步强化了枚举法的应用。 1.3节围绕贪心算法...