Eva

Description

有n个机器，每个机器有2个芯片，每个芯片可以放k个电池。

每个芯片能量是k个电池的能量的最小值。

两个芯片的能量之差越小，这个机器就工作的越好。

现在有2nk个电池，已知它们的能量，我们要把它们放在n个机器上的芯片上，

使得所有机器的能量之差的最大值最小。

第一行，两个正整数，n和k。

第二行，2nk个整数，表示每个电池的能量。

Output

一行一个整数，表示所有机器的能量之差的最大值最小是多少。

2 3
1 2 3 4 5 6 7 8 9 10 11 12

1

2nk <= 10^6, 1 <= pi <= 10^9。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long ll;

char ch[20];

int a[1000001];

const int inf=0x3f3f3f3f;

int n,m,k;

int l,r,mid;

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9')

        {

            if(ch=='-')

                f=-1;

            ch=getchar();

        }

    while(ch>='0'&&ch<='9')

        {

            x=x*10+ch-'0';

            ch=getchar();

        }

    return x*f;

}

inline void P(int x)

{

    int  num=0;

    if(!x)

        {

            putchar('0');

            puts("");

            return;

        }

    while(x>0) ch[++num]=x%10,x/=10;

    while(num) putchar(ch[num--]+48);

    puts("");

}

bool check(int x)

{

    for(int p=1,q=0;q<n;++p)

    {

        if(p-1>q*2*k)

            return false;

        if(a[p+1]-a[p]<=x)

            ++p,++q;

    }

    return true;

}

int main()

{

    n=read();

    k=read();

    m=2*n*k;

    l=0,r=0;

    for(int i=1;i<m+1;i++)

    {

        a[i]=read();

        r=max(r,a[i]);

    }

    sort(a+1,a+m+1);

    while(l<r)

    {

        mid=(l+r)>>1;

        if(check(mid))

            r=mid;   

        l=mid+1;

    }

    printf("%d\n",l);

}