KIDx的解题报告
进入USACO要注册才能看题: http://train.usaco.org/usacogate
题目:【翻译版、是别处的网站】
http://www.wzoi.org/usaco/11%5C304.asp
/*
ID: 1006100071
LANG: C++
TASK: barn1
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define M 205
int a[M];
struct point{
int d, i;
}x[M];
bool cmp (point a, point b)
{
return a.d > b.d;
}
bool cmp2 (point a, point b)
{
return a.i < b.i;
}
int main()
{
/*freopen ("barn1.in", "r", stdin);
freopen ("barn1.out", "w", stdout);*/
int k, n, m, ans = 0, pre, i;
scanf ("%d%d%d", &k, &m, &n);
k = min (k, n); //注意……
k--; //分割点个数
for (i = 0; i < n; i++)
scanf ("%d", a+i);
sort (a, a+n);
for (i = 0; i < n - 1; i++)
x[i].d = a[i+1] - a[i], x[i].i = i;
sort (x, x+n-1, cmp);
sort (x, x+k, cmp2);
pre = a[0]; //pre是第i个组的起点
for (i = 0; i < k; i++)
{
ans += a[x[i].i] - pre + 1; //x[i].i第i个组的终点下标
pre = a[x[i].i+1]; //把下一个元素作为下一组的起点
}
ans += a[n-1] - pre + 1; //最后一组
printf ("%d\n", ans);
return 0;
}
分享到:
相关推荐
从文件 barn1.in 中读入数据。 第 1 行: M , S 和 C(用空格分开) 第 2 到 C+1行: 每行包含一个整数,表示牛所占的牛棚的编号。 输出 输出到文件 barn1.out 中。 单独的一行包含一个整数表示所需木板的最小总长度。 ...
【标题】"usaco-1.rar_barn1" 涉及的是USACO(美国计算机奥林匹克)竞赛中的一道编程题目,名为“Barn1”。USACO是一个旨在提升中学生计算机科学技能的比赛,主要关注算法和编程。在本题中,参赛者需要解决与农业或...
《Big Barn:巨大的牛棚——USACO 动态规划问题解析及测试数据详解》 在计算机科学领域,特别是算法竞赛如USACO(美国计算机奥林匹克)中,动态规划(Dynamic Programming, DP)是一种常被使用的高效解题方法。本...
在压缩包中包含的文件“usaco教程翻译.doc”很可能包含了从基础到进阶的所有USACO教程的翻译,涵盖各个主题,如基本的数据结构(如数组、链表、栈、队列、树和图),排序和搜索算法(如冒泡排序、选择排序、快速排序...
USACO 官网第一到 五章 练习题中文语言官方数据 fps格式支持导入所有OJ ...11 [1.3] 修理牛棚 Barn Repair 12 [1.3] 牛式 Prime Cryptarithm 13 [1.3] 虫洞 wormhole 14 [1.3] 滑雪课程设计Ski Course Design
"Barn Repair"问题是一个贪心算法的应用实例,通过每次选择能覆盖最多牛棚的木板,以达到最小化所需木板数量的目标。贪心算法的关键在于问题能被分解成一系列独立的决策步骤,且局部最优解能导向全局最优解。 4. **...
“Barn Repair”再次强调了贪心算法的应用场景。 ### 五、Chapter4:Advanced algorithms and difficult drills 进入高级算法和困难训练阶段,题目开始涉及更复杂的概念和技巧。例如,“Packing Rectangles”在这...
1.3.1 "Mixing Milk" 和 "Barn Repair" 可能涉及到更复杂的数学模型和动态规划。 1.4.1 "Packing Rectangles" 可能需要理解二维空间的填充问题,这可能涉及到贪心策略或图论。 1.5.1 "Number Triangles" 可能与...
通过阅读译题,可以提前熟悉USACO竞赛的出题风格,了解常见问题类型,如图论、动态规划、贪心算法等。 2. **USACO+1-5.chm**:这部分可能包含了USACO的前五届比赛题目,或者是按照难度分的级别1到5的题目集合。这些...
10. **贪心算法**:在某些情况下,通过每一步都采取局部最优解可以达到全局最优,这就是贪心算法。 通过分析和理解USACO 1.1级别的C++源代码,新手可以逐步掌握这些基本概念和技巧。同时,"Only post for the new ...
USACO,全称为United States Computer Olympiad,是一项面向全球中学生的计算机编程竞赛,旨在提升参赛者的算法设计、问题解决和编程能力。该比赛每年举行,分为青铜、白银、黄金和铂金四个级别,难度逐渐递增。...
4. **贪心策略**:对于部分最优解能得出全局最优解的问题,如活动选择问题或区间调度问题。 5. **回溯和深度优先搜索**:在解决组合优化问题或解谜问题时常见,如八皇后问题或数独填充。 6. **字符串处理**:涉及到...
### USACO 2010-2011 季度竞赛概览与关键信息 #### 一、概述 美国计算机奥林匹克(USACO)是面向全球中学生的计算机科学竞赛,旨在发掘并培养计算机科学领域的年轻人才。USACO 2010-2011 季度竞赛于 2010 年 11 月...
### USACO心得及总结 #### 第一部分 动态规划 **USACO**(美国计算机奥林匹克竞赛)作为一项国际知名的编程竞赛,不仅考验参赛者的编程能力,还对其算法理解和应用有着极高的要求。其中,动态规划(Dynamic ...
更高级的题目可能需要动态规划、回溯法或贪心策略等复杂算法。此外,熟悉字符串操作(如KMP、Rabin-Karp搜索)和数论知识(如模运算、大整数计算)也是必不可少的。 通过反复练习这些测试数据,参赛者不仅可以提高...
usaco上的题目barn1的答案,绝对正确
USACO,全称United States Computer Olympiad,是一项面向全球中学生的计算机编程竞赛,旨在提升参赛者在算法设计、问题解决以及计算机科学基础方面的技能。这个压缩包文件提供了丰富的资源,帮助参赛者或学习者更好...
1. **基础算法**:包括排序(如快速排序、归并排序)、搜索(如二分查找、深度优先搜索、广度优先搜索)、动态规划、贪心策略等。 2. **数据结构**:链表、树(二叉树、平衡树如AVL和红黑树)、图、堆(最大堆、...
【标题】"usaco traning全部数据" 涉及的是一个编程竞赛训练平台——USACO(USA Computing Olympiad)的数据集。USACO是一个专门为美国中学生设计的在线编程竞赛,旨在提升参赛者的算法设计和编程能力,特别是在解决...