http://codeforces.com/contest/985/problem/C
You have m?=?n·k wooden staves. The i-th stave has length ai. You have to assemble n barrels consisting of k staves each, you can use any k staves to construct a barrel. Each stave must belong to exactly one barrel.
Let volume vj of barrel j be equal to the length of the minimal stave in it.
You want to assemble exactly n barrels with the maximal total sum of volumes. But you have to make them equal enough, so a difference between volumes of any pair of the resulting barrels must not exceed l, i.e. |vx?-?vy|?≤?l for any 1?≤?x?≤?n and 1?≤?y?≤?n.
Print maximal total sum of volumes of equal enough barrels or 0 if it‘s impossible to satisfy the condition above.
The first line contains three space-separated integers n, k and l (1?≤?n,?k?≤?105, 1?≤?n·k?≤?105, 0?≤?l?≤?109).
The second line contains m?=?n·k space-separated integers a1,?a2,?...,?am (1?≤?ai?≤?109) — lengths of staves.
Print single integer — maximal total sum of the volumes of barrels or 0 if it‘s impossible to construct exactly n barrels satisfying the condition |vx?-?vy|?≤?l for any 1?≤?x?≤?n and 1?≤?y?≤?n.
4 2 1
2 2 1 2 3 2 2 3
7
2 1 0
10 10
20
1 2 1
5 2
2
3 2 1
1 2 3 4 5 6
0
In the first example you can form the following barrels: [1,?2], [2,?2], [2,?3], [2,?3].
In the second example you can form the following barrels: [10], [10].
In the third example you can form the following barrels: [2,?5].
In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.
思路：
先找把每k个中最小的加起来，这是必须的。然后再把符合要求的从上至下，加在一起。
贪心思想。
不懂请留言，没人看不想写得太详细，况且这题本身不难。
#include<iostream> #include<algorithm> using namespace std; long long a[2000086]; bool book[2000086]; int main() { int n,k,l; cin>>n>>k>>l; for(int i=1;i<=n*k;i++){ cin>>a[i]; } sort(a+1,a+n*k+1); int flag=0; int maxx,minn,t=n*k; long long ans=0; if(a[n]-a[1]>l){cout<<0<<endl;} else{ for(int i=n;i<=n*k;i++){ if(a[i]-a[1]>l){t=i-1;break;} } int flag=0; for(int j=1;j<=t;j+=k){ ans+=a[j];flag++; book[j]=true; if(flag==n){break;} } for(int j=t;j>=1;j--){ if(flag==n){break;} if(!book[j]){ans+=a[j];flag++;} if(flag==n){break;} } cout<<ans<<endl; } }
Codeforce Div-2 985 C. Liebig's Barrels
原文：https://www.cnblogs.com/ZGQblogs/p/9071522.html