题解：AT_abc403_d [ABC403D] Forbidden Difference

· · 题解

没有二分的吗，我来一发。

题目传送门

思路

既然是找一个数能不能被删，且限制下标，不是有序的，就不能用二分了？

我们发现 |B_i-B_j|\ \neq\ D 也就是说这个限制对于排序来说没有作用，所以排序。

排完序后就可以直接二分了吗？

因为我们枚举每个数，从这个数开始往后找，我们只需要找到后直接计数器加一，所以删哪个都一样。

至于删去后的数，直接存数组里打标记，否则会导致我下一次遍历到这个数时又给他用了，但他早已被删了。

有个需要注意的地方：

举个例子：

6 3
2 2 2 5 5 5

这个情况下，我能直接二分到这一堆 5 中间去然后走人吗？这样的话就不好二分了，我们可以往右找，直到没有了或被用了。

还有另一个要注意的地方：

当 d=0 的情况，再举个例子：

10 0
1 2 2 3 3 3 4 4 4 4

很明显这里不能都只删一个，所以要判断情况：当前这剩余数量小于两个的时候只删一个；大于两个的时候就每找一次就删两下，直到剩余数量小于两个的时候，这时只删一个。

代码

#include<bits/stdc++.h>
using namespace std;
int n,d,a[200050],cnt=0,vis[2000050],t[2000050];
int main(){
    cin>>n>>d;
    for(int i = 1 ; i <= n ; i++){
        cin>>a[i];
        t[a[i]]++;
    }
    if(n==1){//特判，我也不知道为什么
        cout<<0;
        return 0;
    }
    sort(a+1,a+n+1);
    for(int i = 1 ; i <= n ; i++){
        int l=i,r=n,ret=0;
        if(!vis[i]){
            while(l<=r){
                int mid=(l+r)/2;
                if(a[i]-a[mid]==-d&&!vis[mid]){
                    ret=mid;
                    l=mid+1;
                }
                else if(a[i]-a[mid]>-d){
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
        }
        if(ret){
            if(ret!=i){
                if(d==0&&t[a[ret]]-2>=1){//0的情况
                    t[a[ret]]-=2;
                    cnt++;
                }
                vis[ret]=1;
                cnt++;
            } 

        }

    }
    cout<<cnt;
    return 0;
}

//1 2 2 2 3 4 5 5 10 10
//1 1 3 4 5

通过记录