题解 CF985C 【Liebig's Barrels】
hicc0305
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，代码：
```cpp
#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;
}
```