[PPS] Electricity Poles (C++)

<Problem>

 

Electricity Poles

𝑛 Electricity poles are on a horizontal line transmitting electricity through an electric wire. Each pole is located at a unique point between 0 and 1,000,000,000, inclusively, on the horizontal line. The intervals between two adjacent points are the same. The Office of Energy wants to select 𝑘 poles among the total of 𝑛 poles to install electricity amplifiers for reliable energy transmission. Considering threats of electromagnetic wave interference, the 𝑘 poles must be selected such that the minimum distance between two selected poles must be as large

as possible. Write a program that finds the minimum distance between two poles of the 𝑘 electricity poles that the Office of Energy will select.

 

 

<Requirements>

Input

• The first line from the standard input has two numbers 𝑛 and 𝑘.
  The first number, 𝑛 stands for the number of electricity poles where 2 ≤ 𝑛 ≤ 100,000. The other number, 𝑘 represents the number of poles to install amplifiers for 2 ≤ 𝑘 ≤ 𝑛 ≤ 100,000.
• Thereafter, 𝑛 lines follow, each of which contains one number that represents 𝑥𝑖, the location of an electricity pole for 1 ≤ 𝑥𝑖 ≤ 1,000,000,000. Note that these numbers are not sorted in any order.

Output

• Print out one number to the standard output within 0.5 seconds.

 

 

 

<Solved>

 

Problem Analysis

• 전봇대 n개가 주어질 때 증폭기를 설치하려고 한다. 
• 설치하고 싶은 증폭기는 k ( 2<= k <= 10000) 이며, 전봇대 사이 최대 사이 거리를 가지고 설치해야한다.
  그러므로 증폭기는 반드시 양 끝에 위치한 전봇대에는 반드시 설치되어야 한다.
• 설치한 전봇대 사이 최대 사이 거리 중 가장 최소인 거리를 구하라 
• 증폭기를 둘 수 있는 자리는 맨 앞과 맨 뒤, 그리고 그 사이에 최소거리가 성립된 거리에 위치한 전봇대이다. 

 

Solution

1. 전봇대 개수 n 과 설치하고 싶은 증폭기 k를 입력받는다. 
2. n의 개수만큼 전봇대의 위치를 입력받고, 이를 오름차순으로 솔팅한다. 
3. min_length와 max_length를 구한다. 첫 min_length는 최소길이가 1이므로 1로 설정하고 max_length는 양 끝 전봇대 사이의 거리로 설정 한다.
4. min_length가 max_length보다 커질때까지 아래를 반복한다
   1. 체크 숫자가 k보다 크다면 avg_length만큼의 거리가 최소거리로 만족했으므로 min_length를 avg_length+1로 설정하여 avg_length값을 재설정 한다.
   2. 체크 숫자가 k보다 크다면 avg_length만큼의 거리가 최소거리로 불만족했으므로 max_length를 avg_length-1로 설정하여 avg_length값을 재설정 한다.
5. max_length를 출력한다

 

Time Complexity

• n (입력받은 전봇대 개수)
• O(n*logn)

 

<Code>

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

using namespace std;

int electricityPoles(int n, int k, vector<int> &poles)
{
    int left = 1, right = poles[n - 1] - poles[0];

    while (1)
    {
        if (left > right)
        {
            break;
        }

        int mid = (left + right) / 2;

        int cnt = 1;
        int start = 0;
        for (int i = 1; i < n; i++)
        {
            if (poles[i] - poles[start] >= mid)
            {
                cnt++;
                start = i;
            }
        }

        if (cnt >= k)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return right;
}

int main()
{
    int n, k;
    vector<int> poles;
    cin >> n >> k;

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

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

    int ans = electricityPoles(n, k, poles);

    cout << ans << endl;
}