Codeforce Div-2 985 C. Liebig's Barrels

http://codeforces.com/contest/985/problem/C

C. Liebig's Barrels
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Codeforce Div-2 985 C. Liebig's Barrels

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.

Input

The first line contains three space-separated integers nk 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.

Output

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.

Examples
input
Copy
4 2 1
2 2 1 2 3 2 2 3
output
Copy
7
input
Copy
2 1 0
10 10
output
Copy
20
input
Copy
1 2 1
5 2
output
Copy
2
input
Copy
3 2 1
1 2 3 4 5 6
output
Copy
0
Note

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[];
bool book[];
int main()
{
int n,k,l;
cin>>n>>k>>l;
for(int i=;i<=n*k;i++){
cin>>a[i];
}
sort(a+,a+n*k+);
int flag=;
int maxx,minn,t=n*k;
long long ans=;
if(a[n]-a[]>l){cout<<<<endl;}
else{
for(int i=n;i<=n*k;i++){
if(a[i]-a[]>l){t=i-;break;}
}
int flag=;
for(int j=;j<=t;j+=k){
ans+=a[j];flag++;
book[j]=true;
if(flag==n){break;}
}
for(int j=t;j>=;j--){
if(flag==n){break;}
if(!book[j]){ans+=a[j];flag++;}
if(flag==n){break;}
}
cout<<ans<<endl;
}
}
上一篇:为什么你写的代码总是有 Bug?用它来保证 Go 代码质量


下一篇:巨人大哥谈Java中的Synchronized关键字用法