Codeforces Round #661. A, B, C번 풀이

내일 열리는 코포에서는 민트 가고 싶다.
어제 코포는 A번에서 생각보다 시간을 많이 끌었다.

A (https://codeforces.com/contest/1399/problem/A)
임의의 i, j(1<=i,j<=n)에 대해 |ai-aj| <= 1을 만족하는 ai와 aj에 대해 최솟값을 제거한 뒤, 하나의 정수로만 구성되는 배열을 만들 수 있는지 답하는 문제이다.
모든 숫자를 오름차순(또는 내림차순)으로 정렬하고 0부터 n - 1까지 돌리면서 차가 2 이상인 경우 NO를 출력해주면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int T;
	cin >> T;
	while (T--) {
		int n, flag = 0;
		vector<int> l;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			l.push_back(a);
		}
		sort(l.begin(), l.end());
		for (int i = 1; i < n; i++) if (abs(l[i] - l[i - 1]) > 1) flag = 1;
 
		cout << (flag ? "NO" : "YES") << "\n";
	}
}

B (https://codeforces.com/contest/1399/standings/participant/98176543#p98176543)
배열 a의 최솟값을 구한 뒤 배열 a를 모두 최솟값으로 만들어주고, 배열 b에 대해서도 동일한 작업을 하면 된다.
이 때, 배열 a를 최솟값으로 만들어주는 과정에서 배열 b도 작게 만들어주면 최소한의 cost로 배열 b가 최솟값을 가지도록 구성할 수 있다.

답의 범위가 int를 넘어가니 long long으로 잡아야 한다. (예제 테스트케이스도 int를 넘어간다)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int T;
	cin >> T;
	while (T--) {
		long long n, minA = 1e9, minB = 1e9, ans = 0;
		cin >> n;
		vector<long long> a(n), b(n);
 
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			minA = min(minA, a[i]);
		}
 
		for (int i = 0; i < n; i++) {
			cin >> b[i];
			minB = min(minB, b[i]);
		}
 
		for (int i = 0; i < n; i++) {
			if (a[i] > minA) {
				long long diff = a[i] - minA;
				b[i] = max(minB, b[i] - diff);
				ans += diff;
			}
			if (b[i] > minB) ans += b[i] - minB;
		}
 
		cout << ans << "\n";
	}
}

C (https://codeforces.com/contest/1399/problem/C)
C번 같은 경우는 고민을 꽤나 오래했다.
사실 좋은 방법이 생각나지 않아서 답이 되는 범위에 대하여 완전 탐색을 돌렸다.
완전 탐색을 하더라도 테스트케이스의 사이즈가 작아서 가능했다.

답이 되는 범위는 최솟값 * 2부터 최댓값 * 2까지이다. 이 범위에 대해서 단순히 탐색만 해주면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int T;
	cin >> T;
	while (T--) {
		int n, ans = 0, m = 1e9, M = 0;
		cin >> n;
		vector<int> l(n);
		for (int i = 0; i < n; i++) {
			cin >> l[i];
			m = min(m, l[i]);
			M = max(M, l[i]);
		}
 
		for (int sum = m; sum <= M * 2; sum++) {
			vector<int> vis(n);
			int temp = 0;
			for (int i = 0; i < n; i++) {
				if (vis[i]) continue;
				for (int j = i + 1; j < n; j++) {
					if (l[i] + l[j] != sum || vis[j]) continue;
					vis[i] = vis[j] = 1;
					temp++;
					break;
				}
			}
 
			ans = max(ans, temp);
		}
 
		cout << ans << "\n";
	}
}