Greedy and Binary Search

Binary search on the answer becomes powerful when a greedy algorithm can correctly decide feasibility for one proposed value. We place K items in available positions to maximize the minimum distance between consecutive placements. For a fixed gap d, putting each next item at the earliest position at least d after the last one preserves maximum room for the suffix. The optimization then searches the monotone gap predicate.

Prerequisites: Binary Search on the Answer; sorting; stays-ahead proofs. Related existing lessons: Binary Search on the Answer.

Build the idea

1. Separate the two proofs

   Sort n positions; duplicates represent distinct available entries and allow a zero-distance placement. Require 2≤K≤n. Feasible(d) means some K entries have consecutive gaps at least d. The outer binary search needs monotonicity, while the inner scan needs a correctness proof. A false checker cannot be repaired by a correct binary-search loop.

2. Build the earliest-placement checker

   Place the first item at the smallest position. Scan forward and place another whenever position−last≥d. Return true as soon as K placements exist. Use low=0 as a known feasible gap and high=largest−smallest+1 as a known infeasible gap. Maintain those meanings until high−low=1; low is then the optimum integer gap.

   $$\mathrm{feasible}\left(d\right)\Rightarrow \mathrm{feasible}(d-1)$$

3. Correctness proof: placements stay ahead

   Compare the greedy placement sequence g with any feasible sequence o for the same gap. g1≤o1 because greedy starts leftmost. If gi≤oi, then o(i+1)≥oi+d≥gi+d and is a candidate for the next placement, so greedy’s earliest feasible g(i+1)≤o(i+1). Induction proves greedy fits at least as many placements as any competitor. Feasible(d) is monotone because a placement satisfying d also satisfies every smaller gap. These two arguments justify both layers.

4. Trace the sample

   Positions [1,2,8,4,9] sort to [1,2,4,8,9], K=3. Gap 3 is feasible with [1,4,8]. Gap 4 starts at 1, then chooses 8 and cannot place a third, so it is infeasible. The best minimum distance is 3. After finding low, a second identical scan reconstructs an actual witness rather than returning only a guessed value.

5. State limits and invariants

   Coordinates are integers within ±10^9, so the span and high fit long long. Numeric range affects only the logarithm of binary-search iterations. The greedy proof uses a line with sorted positions; circular placement, weighted choices or additional forbidden pairs change the feasibility problem. Do not assume every binary-search predicate can be checked by earliest choice.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
bool feasible(const std::vector<long long>&x,int k,long long gap){
    int placed=1;
    long long last=x[0];
    for(int i=1;i<(int)x.size();++i){
        if(x[i]-last>=gap){
            last=x[i];
            if(++placed>=k){
                return true;
            }
        }
    }
    return false;
}
int main(){
    int n,k;
    std::cin>>n>>k;
    std::vector<long long>x(n);
    for(auto&p:x){
        std::cin>>p;
    }
    std::sort(x.begin(),x.end());
    long long low=0,high=x.back()-x.front()+1;
    while(high-low>1){
        long long mid=low+(high-low)/2;
        if(feasible(x,k,mid)){
            low=mid;
        }
        else{
            high=mid;
        }
    } // low feasible, high infeasible.
    std::cout<<low<<'\n';
    int count=1;
    long long last=x[0];
    std::cout<<last;
    for(int i=1;i<n&&count<k;++i){
        if(x[i]-last>=low){
            last=x[i];
            std::cout<<' '<<last;
            ++count;
        }
    }
    std::cout<<'\n';
}

Complexity analysis

O(n log n) sorting plus O(n log(span+2)) checker work and O(n) reconstruction. O(n) stored positions and O(1) checker state. The binary-search endpoints and differences use long long.

Example input and output

Read n K (2≤K≤n≤100000), then n integer positions within ±10^9. Print maximum minimum integer gap and K witness positions in increasing order. Duplicate positions are allowed as separate entries.

Input

5 3
1 2 8 4 9

Output

3
1 4 8

The witness gaps are 3 and 4; no three entries can have both gaps at least 4.

Practical applications

Use when optimizing a threshold whose feasibility becomes easier in one direction, and an exchange/stays-ahead rule solves the decision version. The existing Fundamentals lesson covers binary-search mechanics; this lesson concentrates on why a greedy checker is trustworthy.

Check your understanding

What two facts justify the binary-search optimization?

Put it into practice

Compare every K-position subset for up to eight positions.