洛谷题解:P1209 【[USACO1.3]修理牛棚 Barn Repair】
2024-08-25 22:23:24
原题传送门:https://www.luogu.org/problemnew/show/P1209
首先,这是一道贪心题。
我们先来分析它的贪心策略。
例如,样例:
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
它们之间的差是:
1 2 2 6 1 1 1 4 4 1 1 3 1 9 1 1 1
既然我们要让木板长度最小,那么我们就得空出前m-1个最大的区域,把其他区域累加,再加上一个m(例如3~8的差是8-3=5,而实际木板长度为8-3+1=6,每个木板都多一个,那么m个木板会多出m个)。
代码1(50分代码):
#include <bits/stdc++.h>
using namespace std;
struct node
{
int cow,div;
/*
cow为该牛所占牛棚编号,
div为该点与上一点差,
_为这是一个WA代码,
*/
}_[];
int m,s,c;
bool cmp(node c,node d)
{
return c.div>d.div;
}
int main()
{
int ans=;
scanf("%d%d%d",&m,&s,&c);
scanf("%d",&_[].cow);_[].div=;
for (int i=;i<=c;i++)
{
scanf("%d",&_[i].cow);
_[i].div=_[i].cow-_[i-].cow;
}
sort(_+,_+c+,cmp);
for (int i=m;i<=c;i++) ans+=_[i].div;
ans+=m;
printf("%d\n",ans);
return ;
}
这是一个50分代码。很显然,问题在于:认为输入的编号一定是升序序列。所以,添加abs和sort,代码为:
代码2(80分代码):
#include <bits/stdc++.h>
using namespace std;
struct node
{
int cow,div;
/*
cow为该牛所占牛棚编号,
div为该点与上一点差,
_为这是一个WA代码。
*/
}_[];
int m,s,c;
bool cmp1(node c,node d)
{
return c.cow<d.cow;
}
bool cmp2(node c,node d)
{
return c.div>d.div;
}
int main()
{
int ans=;
scanf("%d%d%d",&m,&s,&c);
scanf("%d",&_[].cow);
for (int i=;i<=c;i++)
scanf("%d",&_[i].cow);
sort(_+,_+c+,cmp1);
for (int i=;i<=c;i++) _[i].div=abs(_[i].cow-_[i-].cow);
sort(_+,_+c+,cmp2);
for (int i=m;i<=c;i++) ans+=_[i].div;
ans+=m;
printf("%d\n",ans);
return ;
}
这个代码很容易被认为是AC代码,其实不然。例如,测试点6,出现了m比c大的情况。那么它肯定不能用m个木板去覆盖。这种时候,我们只要在每个点上都摆一个长度为1的木板就行了,或者说,木板总长即为牛的只数。所以,代码如下:
代码3(100分代码):
//本题解由姆洋题解®提供。姆洋题解,蒟蒻们的题解。
#include <bits/stdc++.h>
using namespace std;
struct node
{
int cow,div,_this,_last;
/*
cow为该牛所占牛棚编号,
div为该点与上一点差,
_this为该点,_last为上一点。
*/
}_[];
int m,s,c;
bool cmp1(node c,node d)
{
return c.cow<d.cow;
}
bool cmp2(node c,node d)
{
return c.div>d.div;
}
int main()
{
int ans=;
scanf("%d%d%d",&m,&s,&c);
if (m>=c) {printf("%d\n",c);return ;}
scanf("%d",&_[].cow);_[]._last=;_[]._this=;
for (int i=;i<=c;i++)
scanf("%d",&_[i].cow);
sort(_+,_+c+,cmp1);
for (int i=;i<=c;i++) _[i].div=abs(_[i].cow-_[i-].cow),_[i]._this=i,_[i]._last=i-;
sort(_+,_+c+,cmp2);
for (int i=m;i<=c;i++) ans+=_[i].div;
ans+=m;
printf("%d\n",ans);
return ;
}
最新文章
- Debian8.2 安装搜狗输入法
- 15款最好的 jQuery Modal(模态窗口)插件
- JAVA基础知识之JDBC——编程步骤及执行SQL
- 【linux】VMware12.0安装
- Qt之QCheckBox
- 数码管字符产生器GenSym 1.0发布
- 修改mysql的root密码
- 鼠标滑过提示title
- SQLite入门与分析(二)---设计与概念
- Jedis
- spring cloud_1_mm_eureka2 eureka集群
- Linux_软件安装_jdk_tomcat_Mysql
- so静态分析进阶练习——一个CreakeMe的分析思路
- linux基本之一
- C# 地磅串口编程
- 多媒体开发之h264中的sps---sps信息提取之帧率
- PyQt5教程——介绍(1)
- linux下添加用户到sudo组
- 在windows x64上部署使用Redis
- Jquery Uploadify多文件上传实例