[規格/c+]2110号:ルータのインストール

質問リンク

アイデア

説明:

最初の家にはルータを設置しなければなりません.
2 3
5
15
18
テストケースがあります

#1

最初の間隔は9です.
5号室にルーターを1台取り付けます.
15日に家に帰ってもう一台入れます.
そして15号室に設置されているルーターと前/後に設置されているルーターの間隔は少なくとも9でなければなりませんが、そうではありませんので、間隔を短くする必要があります.
最終的にルータをインストールせず、すべての家にアクセスしたのでrightをmid-1に調整しました.(間隔を縮める)

#2

間隔は4です.(left = 0, right = 8)
5号室にはもう1台設置されていて、
15日に家に帰って1台詰めます.
15号と18号の間隔が3なので、18号にルーターを取り付けることはできません.
だから間隔を短くします.

#3

間隔は3(左=0、右=3)
現在は間隔が3なので、5日、15日、18日の自宅に3台のルーターを設置することができます.
まず正解を3に設定し、間隔を増やします.(最大間隔を探す問題なので)
現在のテストケースの範囲は狭いため、これで終わります.

問題のテストケース

5 3
1
2
8
4
9

コミットコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int n, c;
	cin >> n >> c;
	int input;
	vector<int> v;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		v.push_back(input);
	}

	sort(v.begin(), v.end());

	int left = 0; 
	int right = v.back(); 
	int ans = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		int beforeSetIdx = 0;  // 공유기를 놓은 첫번째 집
		int cnt = 1; // 첫번째 집에 설치된 공유기

		for (int idx = 1; idx < n; idx++)
		{
			if (v.at(idx) - v.at(beforeSetIdx) >= mid)
			{
				beforeSetIdx = idx;
				cnt++;
			}
		}

		if (cnt >= c)  
		{ // 간격 늘리기
			ans = mid;
			left = mid + 1;
		}
		else // 간격 좁히기
			right = mid - 1;
	}

	cout << ans;

	return 0;
}