336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
입력으로 용액의 특성값이 주어진다. 두용액을 더했을 때 0에 가까운 값을 가지는 두 특성값을 작은 값, 큰 값을 출력한다.
[문제 풀이]
먼저 입력으로 주어지는 수를 정렬을 한다.
- 그런 후 양쪽에 있는 수(새로운 합)를 더한다.
- 더한 수가 현재 저장하고 있는 값(이전 합)보다 작다면 갱신한다.
- 만약 새로운 합이 양수라면 양수쪽 값을 더 작게하기 위해 뒤 위치에서 하나내린다.
- 만약 새로운 합이 음수라면 음수쪽 값을 더 작게하기 위해 앞 위치에서 하나올린다.
- 값을 출력한다.
위 과정으로 구할 수 있다.
[C++ source 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<iostream> struct minheap { int d[1<<18]; int e; minheap() { e = 0; } void clear() { e = 0; } bool empty() { return e == 0; } bool full() { return (e + 1) == (1 << 18); } void push(int i) { if (full()) return; d[++e] = i; int cur = e; while (cur / 2 > 0) { if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]); else break; cur /= 2; } } void pop() { if (empty()) return; d[1] = d[e]; e--; int cur = 1; while (2 * cur <= e) { int child; if (2 * cur + 1 > e) { child = 2 * cur; } else { child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1; } if (d[cur] < d[child]) break; swap(d[cur], d[child]); cur = child; } } void swap(int& a, int& b) { int t = a; a = b; b = t; } int top() { if (empty()) return -1; return d[1]; } }; int mabs(int a) { return (a > 0) ? a : -a; } int im[1 << 18]; minheap PQ; int main() { int N; scanf("%d", &N); for (register int i = 0; i < N; ++i) { scanf("%d", &im[i]); PQ.push(im[i]); } for (register int i = 0; i < N; ++i) { im[i] = PQ.top(); PQ.pop(); } int s = 0; int e = N - 1; int c_diff = 2000000001; int ans[2]; while (s < e) { int diff = im[s] + im[e]; if (diff == 0) { ans[0] = im[s]; ans[1] = im[e]; break; } else if (diff > 0) { if (mabs(c_diff) > mabs(diff)) { c_diff = diff; ans[0] = im[s]; ans[1] = im[e]; } e--; } else if (diff < 0) { if (mabs(c_diff) > mabs(diff)) { c_diff = diff; ans[0] = im[s]; ans[1] = im[e]; } s++; } } printf("%d %d\n", ans[0], ans[1]); return 0; } | cs |