Codeforces Round #661(Div. 3) 문제 해결 보고서

Codeforces Round #661(Div. 3)
A. Remove Smallest
제목의 대의.
만약\a i - a j\≤1 | a{i}-a_{j}|\leq 1\ai --aj\≤1은 mi n(a, a j)min(a {i}, a {j})min(ai, aj)을 삭제할 수 있습니다.
문제풀이의 방향
aa수조를 정렬하고 두 개의 인접한 원소에 대해 1보다 큰 차이를 판단한다
AC 코드

#include 
using namespace std;
int a[100];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
		}
		sort(a + 1, a + n + 1);
		bool flag = true;
		for (int i = 2; i <= n; ++i) {
			if (a[i] - a[i - 1] > 1) {
				flag = false;
				break;
			}
		}
		cout << (flag ? "YES" : "NO") << '
';
	}
	return 0;
}

B. Gifts Fixing
제목의 대의.
aaa와 bbb는 두 개의 서열이 있는데, 당신은 매번 aa 를{i} ai 를 1로 줄이거나 b i b{i} bi 1을 빼거나 동시에 1을 빼면 a 1 = a 2 =. =a n a_{1}=a_{2}=...=a_{n} a1​=a2​=...=an​, b 1 = b 2 = . . . = b n b_{1}=b_{2}=...=b_{n} b1​=b2​=...=bn에 필요한 최소 조작 횟수는 얼마입니까
문제풀이의 방향
분명히 최종 상황은 a1=a2=.=a n = m i n ( a 1 , a 2 , . . . , a n ) a_{1}=a_{2}=...=a_{n}=min(a_{1},a_{2},...,a_{n}) a1​=a2​=...=an​=min(a1​,a2​,...,an​), b 1 = b 2 = . . . = b n = m i n ( b 1 , b 2 , . . . , b n ) b_{1}=b_{2}=...=b_{n}=min(b_{1},b_{2},...,b_{n}) b1​=b2​=...=bn​=min(b1​,b2​,...,bn​)
고려(ai, bi)(a {i}, b {i})(ai, bi), 두 수에 각각 필요한 조작 횟수는 a i -3. m i n a a{i}-min_{a} ai​−mina​, b i − m i n b b_{i}-min_{b} bi -3 minb, 그러면 우리는 분명히 조작 3을 사용하여 그것들의 공통된 부분을 함께 줄일 수 있다. 그러면 그에 필요한 최소 조작수는 m a x(a i -3 m i n a, b i -3 m i n b)max(a {i}-min {a}, b {i}-min {b})max(ai - mina, bi -3 minb)max(ai -
AC 코드

#include 
using namespace std;
typedef long long ll;
ll a[110], b[110];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		ll Mina = LONG_MAX, Minb = LONG_MAX;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
			Mina = min(Mina, a[i]);
		}
		for (int i = 1; i <= n; ++i) {
			cin >> b[i];
			Minb = min(Minb, b[i]);
		}
		ll res = 0;
		for (int i = 1; i <= n; ++i) {
			res += max(a[i] - Mina, b[i] - Minb);
		}
		cout << res << '
';
	}
	return 0;
}

C. Boats Competition
제목의 대의.
aa와 bbb가 두 개의 서열이 있는데, 모듈 (a i, b i) (a {i}, b {i}) (ai, bi) 을 골라서 a 1 + b 1 = a 2 + b 2 =.a k + b k a_{1}+b_{1}=a_{2}+b_{2}=...=a_{k}+b_{k} a1​+b1​=a2​+b2​=...=ak+bk, kkk의 최대치가 얼마냐고 물어봐요.
문제풀이의 방향
n n n 은 50 50 50 50 에 불과하고 1 ≤ a i, b i ≤ n 1\leq a{i},b_{i}\leq n 1 ≤ai,bi≤n,그러면 a i + b i a{i}+b_{i}ai+bi는 100, 100, 100을 넘지 않습니다. 저희 폭력 일괄 ai+b i{i}+b_{i}ai+bi의 값을 탐욕적으로 매칭하면 됩니다
AC 코드

#include 
using namespace std;
typedef long long ll;
int n;
int a[110];
int solve(int x) {
	int res = 0;
	int l = 1, r = n;
	while (true) {
		if (l >= r) break;
		if (a[r] + a[l] > x) --r;
		else if (a[r] + a[l] < x) ++l;
		else {
			++res;
			++l;
			--r;
		}
	}
	return res;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
		}
		sort(a + 1, a + n + 1);
		int nn = n * 2;
		int res = 0;
		for (int i = 1; i <= nn; ++i) {
			res = max(res, solve(i));
		}
		cout << res << '
';
	}
	return 0;
}

D. Binary String To Subsequences
제목의 대의.
0 0 0과 1 11로 구성된 문자열을 여러 개의 서열로 나눌 수 있습니다. 서열마다 같은 두 개의 알파벳이 서로 인접하지 않은 것을 충족시키기 위해 최소한 몇 개의 서열이 있어야 문자의 모든 문자를 다 나누고 문자가 속하는 서열 번호를 출력할 수 있는지 물어보세요.
문제풀이의 방향
우리는 두 개의 대기열을 유지하여 현재 0 0 0으로 끝나는 것과 현재 1 1 1 1로 끝나는 하위 서열 기호를 각각 저장한다. 만약에 s [i] = 0 s [i] = 0이면 1 1 1 대기열이 비어 있지 않으면 우리는 그것을 대기열 끝의 하위 서열로 귀속시키고 대기열을 내보내야 한다. 그렇지 않으면 새 하위 서열의 시작이 된다. s [i] = 1 s [i] = 1 s [i] = 1
AC 코드

#include 
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		string s;
		cin >> s;
		vector<int> v[2];
		int tot = 0;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '0') {
				if (v[1].empty()) a[i] = ++tot;
				else {
					a[i] = a[v[1].back()];
					v[1].pop_back();
				}
				v[0].push_back(i);
			}
			else {
				if (v[0].empty()) a[i] = ++tot;
				else {
					a[i] = a[v[0].back()];
					v[0].pop_back();
				}
				v[1].push_back(i);
			}
		}
		cout << tot << '
';
		for (int i = 0; i < n; ++i) cout << a[i] << " ";
		cout << '
';
	}
	return 0;
}