题解 CF985C 【Liebig's Barrels】

2018-07-22 16:32:30


这是一道还比较容易想到的贪心

我们先将这m个木板按照长度从小到大排个序,这很多人都能想到。

然后,在这n个木桶里,可以知道肯定有一个的容量是a[1]也就是最小的木板的长度。所以,如果a[n]-a[1]>l就不可能成立了,因为a[n]…a[m]都必定大于a[1]+l,不满足要求,而剩下只有n-1根木板,不可能满足被当做n个木桶的容量,所以直接输出零即可。

接下来的贪心策略就可想而知了。要想总容量最大,因为一个木桶的容量确定是a[1],就要让剩下选出的n-1根木板尽可能大,且满足要求。先找到p,使得a[p]-a[1]<=l,a[p+1]-a[1]>l,p就是最大的木桶容积了。

我们把p和后k-1根木板(即m-k+2到m)组成木桶,把p-1和m-2k+3到m-k+1组成木桶……如果p后面的木板不够用了,只能用前面的木板来补了。

具体来举一个栗子:

4 3 17

1 2 3 5 9 13 18 21 22 23 25 26

这里,p=7,也就是大小为18的木板。按照上述贪心理论,我们把18,25,26组成一队(其实不从最后反着取也可以,从p+1开始正着取也可以道理是一样的)。接着把13,22,23组成一队。轮到9的时候,发现只剩下了21可以取,不够了,就只能让5作为木桶容量,把5,9,21分为一组。那么剩下的1,2,3应该也很好懂了。

ok,代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long n,m,k;
long long a[1000100];
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n*m;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n*m+1);
    if(a[n]-a[1]>k)
    {
        cout<<"0";
        return 0;
    }
    int p=n*m;
    while(a[p]-a[1]>k) p--;//求出p
    long long ans=0,num=0,j=p;
    for(int i=n*m;i-(m-1)>p;i=i-(m-1))//取p后面的组队
    {
        ans+=a[j--];
        num++;//记录从p往前多少个已经被取了
    }
    for(int i=1;i<=p-num;i=i+m)//后面不够了,前面剩下的自动隔m(即题目中的k)个作为桶的容积
        ans+=a[i];
    printf("%lld",ans);
    return 0;
}