【Noip模拟 20160929】选数

2024-03-17 19:31:16

题目描述

现在有一排共N个数，你需要从中选出恰好K个。选出K个数后，计算它们两两差值的绝对值的最小值S。你需要确定选出哪K个，才能最大化这个S。

输入数据

输入第一行两个正整数N、K，含义如上。输入第二行N个正整数，依次表示这N个数A1~An。0＜Ai≤10^9。

输出数据

一行一个正整数，S的最大值。

样例输入

11 5

19 585 29 1111 5868 3331 272 4441 2251 868 581

样例输出

数据范围

对于30%30%的数据，N≤18N≤18。

对于60%60%的数据，N≤20N≤20。

对于80%80%的数据，N≤100N≤100。

对于100%100%的数据，N≤100000,K<=NN≤100000,K<=N

题目分析

话说我们上次的那道题，难度应该是NOIP第六题水平了，双向SPFA负环割边fread读优。我们迎来了一道数论题。我们看完题目，一脸懵逼。然后发现“最大的最小，最小的最大”，发现这是一道整体二分。于是我就一遍AC了这道水题。

代码实现

#include<bits/stdc++.h>

using namespace std;

#define RE register int

#define IL inline

#define N 100001

int n,k,a[N],minn=1e9,maxx;

inline char gc(){

    static char buf[],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

}template<class T>inline int read(T&x){

    x=;register char c=gc();

    while(c<)c=gc();

    while(c>)x=(x<<)+(x<<)+(c^),c=gc();

}void write(RE x){

    if (x>)write(x/);

    putchar(x%^);

}inline int check(RE x){

    RE sum=,temp=a[];

    for (RE i=;i<=n;++i)

        if (a[i]>=temp+x) sum++,temp=a[i];

    return sum>=k;

}signed main(){

    freopen("choose.in","r",stdin),freopen("choose.out","w",stdout);

    cin>>n>>k;

    for (RE i=;i<=n;++i) cin>>a[i],maxx=max(maxx,a[i]),minn=min(minn,a[i]);

    sort(a+,a+n+);

    RE r=maxx,l=minn,m,ans=;

    while(l<=r) check(m=(l+r)>>)?ans=m,l=m+:r=m-;

    write(ans);

    return ;

}

代码说明

现在二分答案分为很多个流派，我们学校的许多同学是降临派，我是拯救派，我们已经不流行幸存派了。。。

读者：你个SB，还给我扯，三体看多了吧。

就是说在二分的时候几率答案，二分的方法很多，我不予以展开。这道题的难度啊，NOIP的第二题难度，我5分钟A掉。

码农公寓