题解：AT_abc403_d [ABC403D] Forbidden Difference

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

题目传送门

思路

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

我们发现

|B_i-B_j|\ \neq\ D

也就是说这个限制对于排序来说没有作用，所以排序。

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

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

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

有个需要注意的地方：

举个例子：

CPP

6 3
2 2 2 5 5 5

这个情况下，我能直接二分到这一堆

5

中间去然后走人吗？这样的话就不好二分了，我们可以往右找，直到没有了或被用了。

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

当

d=0

的情况，再举个例子：

CPP

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

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

代码

CPP

#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

通过记录

题解：AT_abc403_d [ABC403D] Forbidden Difference

文章操作

题目传送门

思路

代码

相关推荐

评论

题解：AT_abc403_d [ABC403D] Forbidden Difference