Koios1143的筆記

Zerojudge b542

發表於 更新於 分類於

Zerojudge a007

題敘

https://zerojudge.tw/ShowProblem?problemid=b542
有一群人各有一個身高，求任兩人間身高差為 $k$ 的情況是否存在

想法

先將身高進行排序
那麼每次只須要維護序列的左界與右界，判斷兩者的高度差
如果大於 $k$ 就表示左界要再提升
如果小於 $k$ 就表示右界要再提升
查詢直到差值為 $k$ 即得解

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//By Koios1143
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pii pair<int,int>
using namespace std;
int n,q,k,arr[100010];
string solve(){
	for(int i=0,j=0 ; i<n && j<n ; ){
		int calc=abs(arr[i]-arr[j]);
		if(calc == k)
			return "YES";
		else{
			if(calc < k)
				j++;
			else
				i++;
		}
	}
	return "NO";
}
int main(){
	IOS;
	cin>>n>>q;
	for(int i=0 ; i<n ; i++)
		cin>>arr[i];
	sort(arr,arr+n);
	for(int i=0 ; i<q ; i++){
		cin>>k;
		cout<<solve()<<"\n";
	}
	return 0;
}

複雜度

輸入時間複雜度為 $O(n)$

每筆輸入的處理時間複雜度為 $O(n)$

總時間複雜度約為 $O(n)$