Barn Repair
题目大意:有S个牛栏,其中有C头牛在里面,一些牛栏有牛,一些没有,最大有M块的板子,每块板子的长度可以任意长,用这些板子去拦住所有的牛,使它们都被围住。求最小会有多少牛栏会被围住。
算法分析:isin[S]:表示第i个牛栏里是否有牛。
v[maxn]:表示连续的没有牛的牛栏数。
设一共有top块连续的牛栏里有牛。则可以知道:如果top<=M,则结果就是所有住有牛的牛栏数;否则的话,就需要通过中间没有牛的牛栏连接两块有牛的区域连起来,我们知道,每次这样做都会使所需用的木板数减少,但同时会增加牛栏数。此时,我们很容易想到我们只需每次选择最少数量的没有牛的牛栏块,即只需对数组v进行排序,所求的结果为所有住有牛的牛栏数+v[1]+v[2]+……+v[top-M]。
/*
ID: xxfz014
PROG: barn1
LANG: C++
*/
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
const int maxn = 210;
int m,s,c;
bool isin[maxn];
int main()
{
freopen("barn1.in","r",stdin);
freopen("barn1.out","w",stdout);
scanf("%d%d%d",&m,&s,&c);
int a;
memset(isin,0,sizeof(isin));
for(int i=0;i<c;i++)
{
scanf("%d",&a);
isin[a]=1;
}
int v[maxn],top=0;
int sum=0,c=0;
for(int i=1;i<=s;i++)
{
if(isin[i])
{
sum++;
v[top++]=c;
c=0;
}
else c++;
}
sort(v+1,v+top);
if(m>=top) {printf("%d\n",sum);return 0;}
for(int i=1;i<=top-m;i++)
{
sum+=v[i];
}
printf("%d\n",sum);
return 0;
}
分享到:
相关推荐
从文件 barn1.in 中读入数据。 第 1 行: M , S 和 C(用空格分开) 第 2 到 C+1行: 每行包含一个整数,表示牛所占的牛棚的编号。 输出 输出到文件 barn1.out 中。 单独的一行包含一个整数表示所需木板的最小总长度。 ...
USACO 官网第一到 五章 练习题中文语言官方数据 fps格式支持导入所有OJ ...11 [1.3] 修理牛棚 Barn Repair 12 [1.3] 牛式 Prime Cryptarithm 13 [1.3] 虫洞 wormhole 14 [1.3] 滑雪课程设计Ski Course Design
usaco上的题目barn1的答案,绝对正确
Barn-Burning中文版.doc
Big Barn 巨大的牛棚(usaco动规含测试数据)
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
前端项目-barn,本地存储之上的快速原子持久存储层
C#实现的半透明窗体实例,可完全透明,拖动左侧的滑块向下就可改变透明度,滑块向下透明度提高,向上则透明度降低
Game crystal mines for nintendo with source code
Barn - Laravel 应用程序的 Ansible 剧本 这个存储库提供了专门针对 Laravel 应用程序的 Ansible playbook。 如果您不熟悉 Ansible,它是一个最常用于配置、配置管理和部署的开源工具。 与 Ansible 和这些 playbook ...
chlakh font Thank you for download the font. This font is for PERSONAL USE ONLY
The Advanced Peripheral Bus (APB) is part of the Advanced Microcontroller Bus Architecture (AMBA) protocol family. It defines a low-cost interface that is optimized for minimal power consumption and ...
butch-the-barn-man.github.io:Butch the Barn Man的公共艺术网站
语言:English Bulk and Barn Checkout是一个助手,它在讨论Bulk and Barn网站时增加了购物车的概念 Bulk and Barn Checkout是一个助手,它在讨论Bulk and Barn网站时增加了购物车的概念
c51单片机做一个电子时钟,用到两个四位数码管,加入了蜂鸣器
基于单片机的孵化环境温湿度监控系统,在家禽孵化行业可以有效发挥。
人员疏散时考虑因素 人员行走的模糊规则 利用matlab进行模糊化 考虑人员行走规律
OJ题,有关搜索算法的一道经典的题,算法通过组合数输出的思想一样
Barn2 Media WooCommerce Protected Categories Barn2 Media Woocommerce保护类别" ---------- 泰森云每天更新发布最新WordPress主题、HTML主题、WordPress插件、shopify主题、opencart主题、PHP项目源码、安卓项目...