b542_2 - Error

🔗 前往 ZeroJudge 原題

題目描述

由於 ZeroJudge 網站回傳 500 Server Error，無法取得題目描述。根據提供的程式碼，推測題目可能要求判斷對於給定的數列 a 和一個值 f，是否存在兩個元素 a[p] 和 a[q] (p > q) 使得 a[p] - a[q] == f。題目會有多個 f 值需要測試。

解題思路

程式碼首先讀取數列 a 的大小 n 和查詢次數 m。然後，它讀取數列 a 的元素，並對其進行排序。對於每個查詢值 f，程式碼使用兩個指針 q 和 p，分別指向數列的起始位置。p 指針向右移動，直到 a[p] - a[q] 小於 f 或 p 等於 q。如果 a[p] - a[q] 大於 f，則 q 指針向右移動。如果 a[p] - a[q] 等於 f，則設定一個標誌 c 為 0，表示找到了滿足條件的元素對。最後，根據標誌 c 的值輸出 "YES" 或 "NO"。

複雜度分析

• 時間複雜度: O(n log n + m * n) 排序數列的時間複雜度為 O(n log n)，對於每個查詢，兩個指針的移動時間複雜度為 O(n)，總共有 m 個查詢，因此總時間複雜度為 O(n log n + m * n)。
• 空間複雜度: O(n) 主要用於儲存數列 a，因此空間複雜度為 O(n)。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
long long int n,m,a[100001],f,v;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;++i)
		cin >> a[i];
	sort(a,a+n);
	for(int i=0;i<m;++i){
		cin >> f;
		bool c=1;
		for(int q=0,p=1;p<n&&c;){
			long long int dif=a[p]-a[q];
			if(dif<f||p==q)
				++p;
			else if(dif>f)
				++q;
			else
				c=0;
		}
		if(c)
			cout << "NO\n";
		else
			cout << "YES\n";
	}
}