220 words
1 minutes
[BOJ] 두 수의 합
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
1s | 128MB | (2 ≤ N ≤ 1’000’000, -10^8 ≤ k ≤ 10^8) | Binary Search, Two Pointer |
조건에 서로 다른 수들만 들어오기 때문에 성립하구요. 직관적이고 전형적인 바이너리서치 문제여서 금방 풀었습니다.
정답 코드
이거 fastio 없으면 시간초과 납니다. 조심하셔요
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <random>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MOD 1000000007LL
#define MAX 1'000'000LL
using namespace std;
using ll = long long;
ll nums[1'000'001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t --> 0){
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> nums[i];
sort(nums, nums+n);
int left = 0, right = n-1;
ll diff = 1'000'000'000'000;
ll count = 0;
while(left < right){
ll sumOfLR = nums[left] + nums[right];
if(sumOfLR > k)
right--;
else
left++;
if(diff == abs(k - sumOfLR)) count++;
else if(diff > abs(k - sumOfLR)){
count = 1;
diff = abs(k - sumOfLR);
}
}
cout << count << "\n";
}
return 0;
}
[BOJ] 두 수의 합
https://compy07.github.io/Blog/posts/boj/9024/