앳코더90 - 001 - Yokan Party（★4）

가장 큰 문제는 이녀석들은 일본어라는 것이다.

 

파파고의 도움을 받던가 모르는건 일본어 좀 하는 후배한테 물어보도록 하자

 

https://atcoder.jp/contests/typical90/tasks/typical90_a

001 - Yokan Party（★4）

 

문제 요약만 하자면

Lcm 의 양갱이 있을때 N개의 칼집으로 K번 나눌때 K+ 1개의 조각중 가장 짧은 것의 길이를 최대가 되도록 분할하여라

 

풀이는 짧은 것의 길이를 최대로 하는 값을 파라메트릭 서치 하면된다.

많이 본 유형이라서 해결 할 수 있었다.

 

처리하기 까다로웠던 부분은 자르는 길이가 남았을때를 처리하는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 987654321;

int L, K, N;
vector<ll> v;

bool check(ll mid)
{
	ll count = 0;
	ll bef = 0;

	for (int i = 0; i < v.size(); i++)
	{
		if (v[i] - bef >= mid) 
		{
			count++;
			bef = v[i];
		}
	}

	if (L - bef >= mid)
		count++;

	if (count >= K + 1)
		return true;
	else
		return false;

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> L;

	cin >> K;

	ll p = 0;
	rep(i, N)
	{
		ll tmp;
		cin >> tmp;
		v.push_back(tmp);	
	}

	ll lo = -1;
	ll hi = 1000000002;

	while (lo + 1 < hi)
	{
		ll mid = (lo + hi) / 2;
		if (check(mid))
		{
			lo = mid;
		}
		else
		{
			hi = mid;
		}
	}

	cout << lo;

	return 0;
}