`

【小贪心】USACO Barn Repair

 
阅读更多

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;
}

 

1
0
分享到:
评论

相关推荐

    1005. 【USACO题库】1.3.2 Barn Repair修理牛棚

    从文件 barn1.in 中读入数据。 第 1 行: M , S 和 C(用空格分开) 第 2 到 C+1行: 每行包含一个整数,表示牛所占的牛棚的编号。 输出 输出到文件 barn1.out 中。 单独的一行包含一个整数表示所需木板的最小总长度。 ...

    usaco-1.rar_barn1

    【标题】"usaco-1.rar_barn1" 涉及的是USACO(美国计算机奥林匹克)竞赛中的一道编程题目,名为“Barn1”。USACO是一个旨在提升中学生计算机科学技能的比赛,主要关注算法和编程。在本题中,参赛者需要解决与农业或...

    Big Barn 巨大的牛棚(usaco动规含测试数据)

    《Big Barn:巨大的牛棚——USACO 动态规划问题解析及测试数据详解》 在计算机科学领域,特别是算法竞赛如USACO(美国计算机奥林匹克)中,动态规划(Dynamic Programming, DP)是一种常被使用的高效解题方法。本...

    USACO官网93题fps格式 OJ题库

    USACO 官网第一到 五章 练习题中文语言官方数据 fps格式支持导入所有OJ ...11 [1.3] 修理牛棚 Barn Repair 12 [1.3] 牛式 Prime Cryptarithm 13 [1.3] 虫洞 wormhole 14 [1.3] 滑雪课程设计Ski Course Design

    usaco.rar_USACO 翻译 下载_usaco _usaco 翻译

    在压缩包中包含的文件“usaco教程翻译.doc”很可能包含了从基础到进阶的所有USACO教程的翻译,涵盖各个主题,如基本的数据结构(如数组、链表、栈、队列、树和图),排序和搜索算法(如冒泡排序、选择排序、快速排序...

    usaco教程翻译

    "Barn Repair"问题是一个贪心算法的应用实例,通过每次选择能覆盖最多牛棚的木板,以达到最小化所需木板数量的目标。贪心算法的关键在于问题能被分解成一系列独立的决策步骤,且局部最优解能导向全局最优解。 4. **...

    USACO总结

    “Barn Repair”再次强调了贪心算法的应用场景。 ### 五、Chapter4:Advanced algorithms and difficult drills 进入高级算法和困难训练阶段,题目开始涉及更复杂的概念和技巧。例如,“Packing Rectangles”在这...

    USACO英汉对照题目

    1.3.1 "Mixing Milk" 和 "Barn Repair" 可能涉及到更复杂的数学模型和动态规划。 1.4.1 "Packing Rectangles" 可能需要理解二维空间的填充问题,这可能涉及到贪心策略或图论。 1.5.1 "Number Triangles" 可能与...

    usaco 合集usaco 合集usaco 合集

    通过阅读译题,可以提前熟悉USACO竞赛的出题风格,了解常见问题类型,如图论、动态规划、贪心算法等。 2. **USACO+1-5.chm**:这部分可能包含了USACO的前五届比赛题目,或者是按照难度分的级别1到5的题目集合。这些...

    USACO 1.1 c++源程序

    10. **贪心算法**:在某些情况下,通过每一步都采取局部最优解可以达到全局最优,这就是贪心算法。 通过分析和理解USACO 1.1级别的C++源代码,新手可以逐步掌握这些基本概念和技巧。同时,"Only post for the new ...

    USACO题集及答案

    USACO,全称为United States Computer Olympiad,是一项面向全球中学生的计算机编程竞赛,旨在提升参赛者的算法设计、问题解决和编程能力。该比赛每年举行,分为青铜、白银、黄金和铂金四个级别,难度逐渐递增。...

    usaco历年测试数据

    4. **贪心策略**:对于部分最优解能得出全局最优解的问题,如活动选择问题或区间调度问题。 5. **回溯和深度优先搜索**:在解决组合优化问题或解谜问题时常见,如八皇后问题或数独填充。 6. **字符串处理**:涉及到...

    usaco 2010-2011

    ### USACO 2010-2011 季度竞赛概览与关键信息 #### 一、概述 美国计算机奥林匹克(USACO)是面向全球中学生的计算机科学竞赛,旨在发掘并培养计算机科学领域的年轻人才。USACO 2010-2011 季度竞赛于 2010 年 11 月...

    usaco心得及总结

    ### USACO心得及总结 #### 第一部分 动态规划 **USACO**(美国计算机奥林匹克竞赛)作为一项国际知名的编程竞赛,不仅考验参赛者的编程能力,还对其算法理解和应用有着极高的要求。其中,动态规划(Dynamic ...

    USACO历年比赛测试数据:2003年

    更高级的题目可能需要动态规划、回溯法或贪心策略等复杂算法。此外,熟悉字符串操作(如KMP、Rabin-Karp搜索)和数论知识(如模运算、大整数计算)也是必不可少的。 通过反复练习这些测试数据,参赛者不仅可以提高...

    barn1的答案

    usaco上的题目barn1的答案,绝对正确

    USACO翻译及题解

    USACO,全称United States Computer Olympiad,是一项面向全球中学生的计算机编程竞赛,旨在提升参赛者在算法设计、问题解决以及计算机科学基础方面的技能。这个压缩包文件提供了丰富的资源,帮助参赛者或学习者更好...

    USACO历年比赛测试数据:2005年

    1. **基础算法**:包括排序(如快速排序、归并排序)、搜索(如二分查找、深度优先搜索、广度优先搜索)、动态规划、贪心策略等。 2. **数据结构**:链表、树(二叉树、平衡树如AVL和红黑树)、图、堆(最大堆、...

    usaco traning全部数据

    【标题】"usaco traning全部数据" 涉及的是一个编程竞赛训练平台——USACO(USA Computing Olympiad)的数据集。USACO是一个专门为美国中学生设计的在线编程竞赛,旨在提升参赛者的算法设计和编程能力,特别是在解决...

Global site tag (gtag.js) - Google Analytics