[D5] 7730. 나무 깎는 홍준

#include <stdio.h>
int tree[1000000];
int tree_amount = 0;
int want_to_tree_amount = 0;
int available(int mid) {
	long long buffer = 0;
	for (int i =tree_amount-1; i >0; i--) {
		if (tree[i] > mid) {
			buffer += tree[i] - mid;
		}
		if (tree[i] < mid)
			break;
	}	
	if (buffer >= want_to_tree_amount)
		return 1;
	return 0;
}
void quickSort(int first, int last)
{
	int pivot;
	int i;
	int j;
	int temp;

	if (first < last)
	{
		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (tree[i] <= tree[pivot] && i < last)
			{
				i++;
			}
			while (tree[j] > tree[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = tree[i];
				tree[i] = tree[j];
			tree[j] = temp;
			}
		}

		temp = tree[pivot];
		tree[pivot] = tree[j];
		tree[j] = temp;

		quickSort(first, j - 1);
		quickSort(j + 1, last);
	}
}
int main() {
	int test_case = 0;
	scanf("%d",&test_case);
	for (int q = 0; q < test_case; q++) {
		
		scanf("%d %d", &tree_amount, &want_to_tree_amount);
		int max = 0;
		for (int i = 0; i < tree_amount; i++) {
			scanf("%d", &tree[i]);
			if (tree[i] > max)
				max = tree[i];
		}
		quickSort(0, tree_amount - 1);
		int cut_point = 0;
		int low = 1;
		int mid =0;
		int result = 0;
		while (low<=max) {
			mid = (max + low) / 2;
			if (available(mid)) {
				if (mid > result)
					result = mid;
				low = mid+1;
			}
			else {
				max = mid-1;
			}
		
		}
		printf("#%d %d\n", q + 1, result);
	}

	return 0; 
}