e536 - 10487 - Closest Sums
題目描述
題目給定一個整數集合和一系列查詢。對於每個查詢，需要找到集合中兩個數字的和，使其最接近給定的查詢數字。
解題思路
首先，計算所有可能的數字對的和，並將它們儲存在一個集合 ans 中，以避免重複。然後，將集合轉換為一個向量 vct，以便進行排序。對於每個查詢數字 k，使用 lower_bound 在已排序的向量中找到最接近 k 的數字。比較 k 與 vct[it] 和 vct[it-1] 的距離，選擇距離最小的那個作為最接近的和。
複雜度分析
- 時間複雜度: O(n^2 + m log n)，其中 n 是輸入集合的大小，m 是查詢的數量。計算所有數字對的和需要 O(n^2) 的時間。將集合轉換為向量並排序需要 O(n log n) 的時間。對於每個查詢，使用
lower_bound進行二分查找需要 O(log n) 的時間，總共需要 O(m log n) 的時間。 - 空間複雜度: O(n^2)，因為最壞情況下，集合
ans可能需要儲存所有可能的數字對的和。
程式碼
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int a[1001],n,m,ca,k;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)break;
for(int i=0;i<n;++i)
cin >> a[i];
cin >> m;
cout << "Case " << ++ca << ":\n";
set <int> ans;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
ans.insert(a[i]+a[j]);
vector <int> vct;
for (set<int>::iterator it = ans.begin(); it != ans.end(); it++)
vct.push_back(*it);
n = vct.size();
while(m--){
cin >> k;
int it=(lower_bound(vct.begin(),vct.end(),k)-vct.begin());
if(it!=0&&(it==n||vct[it]-k>k-vct[it-1]))
--it;
cout << "Closest sum to " << k << " is " << vct[it] << ".\n";
}
}
}