swea 19342 국가행정 c++

• 접근방식

  parametric search를 기억하자!

• 해답코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int prefix[10005];
int leg[10005];

priority_queue<pair<int, int>> pq;

int* population;
int dist[10005];


void init(int N, int mPopulation[])
{
	population = mPopulation;

	while (!pq.empty()) {
		pq.pop();
	}

	memset(leg, 0, sizeof leg);
	memset(prefix, 0, sizeof prefix);

	// 누적합으로 각 거리 저장, -1곱해줘서 id저장 -> id가 적은게 먼저 나오게끔
	for (int i = 1; i < N; i++) {
		prefix[i] = (mPopulation[i - 1] + mPopulation[i]);
		pq.push({ prefix[i], -1 * i });
		dist[i] = prefix[i];
	}



	return;
}

int expand(int M)
{
	int ret = 0;

	for (int i = 0; i < M; i++) {
		int cur_dist = pq.top().first;
		int cur = -1 * pq.top().second;
		pq.pop();
		leg[cur]++;

		prefix[cur] = dist[cur] / (leg[cur] + 1);
		pq.push({ prefix[cur], -1 * cur });
		ret = prefix[cur];
	}

	return ret;
}

int calculate(int mFrom, int mTo)
{
	int ret = 0;
	if (mFrom > mTo) { //mFrom, mTo 순서 맞춰주기!!
		swap(mFrom, mTo);
	}
	for (int i = mFrom + 1; i <= mTo; i++) {
		ret += prefix[i];
	}
	return ret;
}

// Parametric search : 가장 큰 선거구의 인구수가 최소가 되게끔.
int divide(int mFrom, int mTo, int K)
{
	int start = 1, end = (int)1e7;
	while (start < end) {
		int mid = (start + end) / 2;
		int cnt = 0; // 선거구 수
		for (int i = mFrom; i <= mTo && cnt <= K; cnt++) {
			int sum = 0, j = i;
			while (j <= mTo && sum + population[j] <= mid) {
				sum += population[j++];
			}
			i = j;
		}
		if (cnt <= K) { // 선거구 인구가 높으면 K보다 덜 나뉘니까
			end = mid;
		}
		else {
			start = mid + 1; // 선거구 인구가 낮으면 K보다 더 나뉘니까
		}
	}

	return end;
}