Educational Codeforces Round 64 -C（二分）

题目链接：https://codeforces.com/contest/1156/problem/C

题意：给出n个数和整形数z，定义一对数为差>=z的数，且每个数最多和一个数组成对，求最多有多少对。

思路：先按升序排序，在区间[0,n/2]二分答案即可，判断m是否满足条件利用贪心思想，即看前x个数和后x个数是否能对应组成对。

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

int n,z,a[];

bool judge(int x){

    bool ans=true;

    for(int i=;i<x;++i)

        if(a[i]+z>a[n+i-x]){

            ans=false;

            break;

        }

    return ans;

}

int main(){

    scanf("%d%d",&n,&z);

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

        scanf("%d",&a[i]);

    sort(a,a+n);

    int l=,r=n/,m;

    while(l<=r){

        m=(l+r)>>;

        if(judge(m)) l=m+;

        else r=m-;

    }

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

    return ;

}

巴特西

Educational Codeforces Round 64 -C（二分）

最新文章

热门文章