欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷题解: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;
}