51nod 1278【贪心】

主要这道题没有包含的情况，所以直接搞个左端，然后对于每个二分求一下>right的最近的位置j，那么ans就会增加 j 以后的；

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <queue>

using namespace std;

const int N=5e4+10;

struct asd{

    int x,y;

};

asd q[N];

int n;

bool cmp(asd a,asd b)

{

    return a.x<b.x;

}

int Find(int s,int e,int tmp)

{

    int left=s;

    int right=e;

    while(left <= right)

    {

        int mid = (left+right) >> 1;

        if(q[mid].x > tmp)

            right = mid-1;

        else

            left = mid+1;

    }

    return left;

}

int main()

{

    int d,r;

    scanf("%d",&n);

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

    {

        scanf("%d%d",&d,&r);

        q[i].x=d-r;

        q[i].y=d+r;

    }

    sort(q,q+n,cmp);

    int j;

    int ans=0;

    for(int i=0;i<n-1;i++)

    {

        j=Find(i+1,n-1,q[i].y);

        ans+=n-j;

    }

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

    return 0;

}

巴特西

51nod 1278【贪心】

最新文章

热门文章