洛谷题解:P1209 【[USACO1.3]修理牛棚 Barn Repair】
程序员文章站
2022-10-18 23:52:03
原题传送门:https://www.luogu.org/problemnew/show/P1209 首先,这是一道贪心题。 我们先来分析它的贪心策略。 例如,样例: 4 50 18 3 4 6 8 1415 16 17 2125 26 27 30 31 40 41 42 43 它们之间的差是: 1 ......
原题传送门: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代码, */ }_[201]; int m,s,c; bool cmp(node c,node d) { return c.div>d.div; } int main() { int ans=0; scanf("%d%d%d",&m,&s,&c); scanf("%d",&_[1].cow);_[1].div=0; for (int i=2;i<=c;i++) { scanf("%d",&_[i].cow); _[i].div=_[i].cow-_[i-1].cow; } sort(_+1,_+c+1,cmp); for (int i=m;i<=c;i++) ans+=_[i].div; ans+=m; printf("%d\n",ans); return 0; }
这是一个50分代码。很显然,问题在于:认为输入的编号一定是升序序列。所以,添加abs和sort,代码为:
代码2(80分代码):
#include <bits/stdc++.h> using namespace std; struct node { int cow,div; /* cow为该牛所占牛棚编号, div为该点与上一点差, _为这是一个wa代码。 */ }_[201]; 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=0; scanf("%d%d%d",&m,&s,&c); scanf("%d",&_[1].cow); for (int i=2;i<=c;i++) scanf("%d",&_[i].cow); sort(_+1,_+c+1,cmp1); for (int i=2;i<=c;i++) _[i].div=abs(_[i].cow-_[i-1].cow); sort(_+1,_+c+1,cmp2); for (int i=m;i<=c;i++) ans+=_[i].div; ans+=m; printf("%d\n",ans); return 0; }
这个代码很容易被认为是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为上一点。 */ }_[201]; 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=0; scanf("%d%d%d",&m,&s,&c); if (m>=c) {printf("%d\n",c);return 0;} scanf("%d",&_[1].cow);_[1]._last=0;_[1]._this=1; for (int i=2;i<=c;i++) scanf("%d",&_[i].cow); sort(_+1,_+c+1,cmp1); for (int i=2;i<=c;i++) _[i].div=abs(_[i].cow-_[i-1].cow),_[i]._this=i,_[i]._last=i-1; sort(_+1,_+c+1,cmp2); for (int i=m;i<=c;i++) ans+=_[i].div; ans+=m; printf("%d\n",ans); return 0; }
上一篇: Lyndon Word学习笔记