BOJ 1114-丸太裁断

タイムアウトメモリ制限正解の送信正解正解正解正解率2秒128 MB 277455233818.820%
質問する
伐採労働者の白銀陣は木を紙工場に運ばなければならない.しかし、丸太の長さが長すぎてトラックに入れないので、いくつかに分けます.
原木の長さはLcmです.しかも原木の特定の位置でしか切断できません.丸木を剪定できる位置がありますが、この位置は丸木の一番左からの距離です.白銀陣はせいぜいC号丸木を切り落とすことができる.
このとき、丸太の最長破片を小さくするプログラムを作成してください.
入力
1行目はL,K,Cです.Lは10000000以下の自然数であり、Kは丸太の剪定可能な位置の個数である.KとCは10000以下の自然数である.2行目は、丸太をトリミングできる位置を示します.
しゅつりょく
1行目は2つの数を出力します.1番目の数字は最長の破片長で、2番目の数字は1番目のカットの位置を出力します.可能な場合は、初期クリップ位置が小さいものを出力します.
に近づく
10億を超える数字を見ると、この探索を思い出した.
だからこの探索で協力して、実現できる実現が現れた.
最長の破片の長さは二分探索で求めればよい.
各ナビゲーションでmid値が長さの場合、C番号以下にカットできるかどうかを確認できます.
Cサイズを超えてカットすると、長さを増やしたり、逆に長さを短くしたりすることができます.
次に、最初のカットの位置を最小にするために、後ろからカットを開始します.
に答える
1〜L値を基準として二分探索を行った.
便宜上arrは最初のインデックスに0を追加し,最後のインデックスにLを追加した.
各ナビゲーションで使用されるsolve関数について、カットするcnt値がCより小さいかどうかを返します.
ここで、cntがCより小さい場合、最初のクリップの位置を最初のインデックスとします.
cntはsum値を基準にして、後でカットが必要かどうかをチェックします.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int L, K, C, answer, tmp, first, arr[10002];

bool solve(int len)
{
	int cnt = 0, sum = 0;
	tmp = -1;
	FDOWN(i, K - 1, 0)
	{
		if (sum + arr[i + 1] - arr[i] > len)
		{
			cnt++;
			sum = arr[i + 1] - arr[i];
			if (sum > len) return false;
			tmp = i + 1;
		}
		else
		{
			sum += arr[i + 1] - arr[i];
		}
	}
	if (cnt < C) tmp = 1;
	return cnt <= C;
}

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

	CIN3(L, K, C);
	arr[0] = 0, arr[K + 1] = L;
	FUP(i, 1, K) CIN(arr[i]);
	K++;
	sort(arr, arr + K);
	int l = 1, r = L;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (solve(mid))
		{
			answer = mid;
			first = tmp;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	COUT2(answer, arr[first]);


	return 0;
}