백준 25386 라즈베리 파이

https://www.acmicpc.net/problem/25386

• 그리디 알고리즘, 애드 혹
• 풀이

1. M과 N이 같을 때, 라즈베리 배열의 모든 칸이 차있으므로 라즈베리를 이동할 수 없습니다. 이 경우엔 a = b가 아닐 시 -1을 출력합니다.
2. 두 참가자의 원하는 라즈베리의 위치가 중복일 시에도 충족되게 나눠줄 수 없습니다. 이 경우엔 -1를 출력합니다.

라즈베리의 원형배열을 일차원 배열처럼 생각합니다. 배정한 라즈베리 파이의 순서를 유지하는 한, 일차원 배열을 계속 확장할 수 있습니다.
a,b 배열을 pair로 묶고 b를 기준, 오름차순으로 정렬했습니다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
const char en = '\n';
const int INF = (int)1e9 + 7;
const int mod = (int)1e9 + 7;

bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second < b.second;
}

int main(void) {
	fast;

	int m, n; cin >> m >> n;
	vector<pair<ll, ll>> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i].first;
	for (int i = 0; i < n; ++i) cin >> a[i].second;

	if (m == n) {
		for (int i = 0; i < n; ++i) {
			if (a[i].first != a[i].second) {
				cout << -1 << en; return 0;
			}
		}
		cout << 0 << en; return 0;
	}

	sort(a.begin(), a.end(), cmp);
	for (int i = 0; i < n - 1; ++i) {
		if (a[i].second == a[i + 1].second) {
			cout << -1 << en; return 0;
		}
	}

	ll ans = 0, cnt = 0;

	for (int i = 0; i < n - 1; ++i) {
		if (a[i].first > a[i + 1].first) {
			double ce = ceil(((double)a[i].first - (double)a[i + 1].first) / (double)m)*(double)m;
			a[i + 1].first += ce;
		}
	}

	for (int i = 0; i < n; ++i) {
		if (a[i].first + (cnt*m) < a[i].second) {
			cnt += 1;
		}
	}

	for (int i = 0; i < n; ++i) a[i].first += cnt * m;

	if (a.front().first + m <= a.back().first) {
		cout << -1 << en; return 0;
	}
	for (int i = 0; i < n; ++i) ans += a[i].first - a[i].second;
	cout << ans << en;

	return 0;
}

• 예제에 관한 풀이 그림 첨부
  순서대로 입력 예제 1,2 입니다.

• 라즈베리 배열은 원래 원형 배열이므로, 정렬된 a 배열의 마지막 조각은 처음 a 조각 + M 보다 크거나 같아야 합니다. ( if(a.front().first + m <= a.back().first 부분입니다.)

• 참가자에게 배정한 파이 조각 위치는 참가자가 원하는 파이 조각의 번호보다 커야합니다.

• 올해 진행된 UCPC 문제들을 몇 문제 풀어봤습니다. 다들 난이도가 상당히 어려웠고, 이 문제는 거진 3일 정도 생각하여 푼 문제였습니다.