POJ 2456 Aggressive cows (二分 + 貪心)

#include <stdio.h>

int numOfStalls, numOfCows;
int position[100001];
int heapSize;

void maxHeapify(int parent){
	int largest = parent;
	int left = parent << 1;
	if (left <= heapSize && position[left] > position[largest])
		largest = left;
	int right = (parent << 1) + 1;
	if (right <= heapSize && position[right] > position[largest])
		largest = right;
	if (largest != parent){
		int temp = position[largest];
		position[largest] = position[parent];
		position[parent] = temp;
		maxHeapify(largest);
	}
}

void buildMaxHeap(){
	int stall;
	for (stall = heapSize >> 1; stall >= 1; stall--)
		maxHeapify(stall);
}

void heapSortPositions(){
	buildMaxHeap();
	int stall;
	for (stall = numOfStalls; stall > 1; stall--){
		int temp = position[stall];
		position[stall] = position[1];
		position[1] = temp;
		heapSize--;
		maxHeapify(1);
	}
}

int canPut(int distance){
	int prePosition = position[1];
	int cowsInStall = 1;
	int stall;
	for (stall = 2; stall <= numOfStalls; stall++)
		if (position[stall] - prePosition >= distance){
			cowsInStall++;
			if (cowsInStall == numOfCows)
				return 1;
			prePosition = position[stall];
		}
	return 0;	
}

int main(){

	scanf("%d%d", &numOfStalls, &numOfCows);
	int stall;
	for (stall = 1; stall <= numOfStalls; stall++)
		scanf("%d", &position[stall]);
	
	heapSize = numOfStalls;
	heapSortPositions();

	int min = 0;
	int max = position[numOfStalls] - position[1];
	int result = 0;
	//因為要确定任意兩個牛棚之間的最短距離之後才能确定能不能容下所有的牛，是以要二分答案
	while (min <= max){
		int mid = (min + max) >> 1;
		if (canPut(mid)){
			if (mid > result)
				result = mid;
			min = mid + 1;
		}
		else 
			max = mid - 1;
	}

	printf("%d\n", result);
	return 0;
}