NKSGAME - VOI08 Trò chơi với dãy số

Problem

https://vn.spoj.com/problems/NKSGAME

https://oj.vnoi.info/problem/NKSGAME

Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:

b1, b2, ..., bn

còn dãy số mà bạn thứ hai chọn là

c1, c2, ..., cn

Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |bi+cj|.

Ví dụ

Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).

Yêu cầu

Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.

Dữ liệu

Dòng đầu tiên chứa số nguyên dương n (n ≤ 10^5)
Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 10^9, i=1, 2, ..., n)
Dòng thứ hai chứa dãy số nguyên c1, c2, ..., cn (|ci| ≤ 10^9, i=1, 2, ..., n)

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Kết quả

Ghi ra giá nhỏ nhất tìm được.

Ràng buộc

60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.

Ví dụ

Input
2
1 -2
2 3

Outut
0

Tutorial

Cần tìm hai chỉ số i, j từ 2 mảng a[] và b[] sao cho |a[i]+b[j]| min. N <= 1e5, do đó ta có thể sắp xếp mảng a[], sau đó duyệt từng phần tử j của mảng b[], chặt nhị phân trên mảng a[] đã được sort để tìm phần tử i gần với giá trị -b[j] nhất.

Có thể sử dụng hàm lower_bound() trong C++.

Submission

NKSGAME.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef unsigned long long ull;

#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define EL printf("\n")
#define sz(A) (int) A.size()
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


const int N = 1e5+5;
int n, a[N], b[N];

void update(int i, int j, int &res) {
	if (0 <= i && i < n && abs(a[i] + b[j]) < res)
		res = abs(a[i] + b[j]);
}

int main() {
//  freopen("INP.TXT", "r", stdin);
//  freopen("OUT.TXT", "w", stdout);

	scanf("%d", &n);
	FOR(i,0,n-1) scanf("%d", &a[i]);
	FOR(i,0,n-1) scanf("%d", &b[i]);

	sort(a, a+n);

	int res = abs(a[0] + b[0]);
	FOR(j,0,n-1) {
		int i = lower_bound(a, a+n, -b[j])-a;
		update(i, j, res);
		update(i-1, j, res);
	}

	printf("%d\n", res);

	return 0;
}

Tutorial SPOJ