P1209 修理牛棚

https://www.luogu.org/problem/show?pid=1209

贪心:
先把连着的牛们用板连起来(相连的几头牛称为),如果块数>m,则需要连板,显然把牛群中间相隔最短的连起来,长度就需要加上补上的这块。

#include<iostream>//减板 
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio> 
using namespace std;
int m,s,c,ansl=0,numb=0,ge[10000],cnt=0,maxn=0;
bool f[300];
int main()
{
    scanf("%d%d%d",&m,&s,&c);
    for(int i=1;i<=c;i++)
    {
        int x;
        scanf("%d",&x);
        f[x]=true;
        maxn=max(maxn,x);
    }
    int j;
    for(int i=1;i<=maxn;i+=j)
    {
        int k=i+1,numl=0;
        j=0;
        if(f[i]&&!f[k]&&k<=maxn)
        {
            while(!f[k]&&k<=maxn)
            {
                numl++;
                k++;
            }
            ge[++cnt]=numl;
        }
        j=k-i;
    }
    j=1;
    for(int i=1;i<=maxn;i+=j)
    {
        j=1;
        if(f[i])
        {
            while(f[i+j])
             j++;
            numb++;
        }
        else continue;
    }
    sort(ge+1,ge+cnt+1);
    ansl=c;
    j=0;
    while(numb>m)
    {
        j++;
        ansl+=ge[j];
        numb--; 
    }

    printf("%d",ansl);
    return 0;
}
原文地址:https://www.cnblogs.com/dfsac/p/6819751.html