原题传送门：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("%dn",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("%dn",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("%dn",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("%dn",ans); return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/605712.html