Luogu p1873 [coci 2011/2012 5] Eko / tree cutting dichotomy

# [COCI 2011/2012 #5] EKO / Cut down trees

## Title Description

Lumberjack Mirko Need to cut $M$ Meters of wood . Yes Mirko It's a simple job for me , Because he has a beautiful new logging machine , You can cut down forests like wildfire . however ,Mirko Only one row of trees is allowed to be cut down .

Mirko The work flow of the logging machine is as follows ：Mirko Set a height parameter $H$（ rice ）, The logging machine raises a huge saw blade to a height $H$, And saw off all the trees $H$ High part （ Of course , Trees are no higher than $H$ The part of the meter remains the same ）.Mirko You get the sawn part of the tree . for example , If the height of a row of trees is $20,15,10$ and $17$,Mirko Raise the saw blade to $15$ Height of meters , After cutting, the remaining height of the tree will be $15,15,10$ and $15$, and Mirko From the $1$ The tree gets $5$ rice , From $4$ The tree gets $2$ rice , Get... Together $7$ Rice wood .

Mirko Pay great attention to ecological protection , So he won't cut too much wood . That's why he set the saw blade of the logging machine as high as possible . Please help Mirko Find the maximum integer height of the logging machine saw blade $H$, So that he can get at least $M$ rice . let me put it another way , If it rises again $1$ rice , He will not get $M$ Rice wood .

## Input format

The first $1$ That's ok $2$ It's an integer $N$ and $M$,$N$ Indicates the number of trees ,$M$ The total required length of wood .

The first $2$ That's ok $N$ An integer representing the height of each tree .

## Output format

$1$ It's an integer , Indicates the highest height of the saw blade .

## Examples #1

### The sample input #1

```
4 7
20 15 10 17
```

### Sample output #1

```
15
```

## Examples #2

### The sample input #2

```
5 20
4 42 40 26 46
```

### Sample output #2

```
36
```

## Tips

about  100\%100%  Test data for ,1≤N≤10^6,1≤M≤2×10^9, The height of the tree  <10^9, The sum of the height of all trees  >M.

.

Ideas ：

Simple dichotomy , This question is obviously a binary search for the right H, Then determine the boundary and check Function . The boundary is the height range of the tree ,check Function is to judge whether we can get M Above the height .

AC Code ：

#include<bits/stdc++.h>
using namespace std;
const int  N = 1e6 + 10;
int n, m,a[N],minh=2e9,maxh;
long long h;
bool check(int mid) {
	long long cnt=0;
	for(int i=0;i<n;i++){
		
		if (a[i] >= mid)cnt += a[i] - mid;
	}
	if (cnt >= m)return true;
	else return false;

}
void bs(int l, int r) {
	
	// Two points to determine the highest suitable height , Search from the height range of the tree 
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (check(mid))l = mid;
		else r = mid - 1;

	}

	h = l;
}
int main(){
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {

		scanf("%d", &a[i]);
		if (minh > a[i])minh = a[i];
		if (maxh < a[i])maxh = a[i];
	}
	
	sort(a, a + n);

	bs(minh, maxh);
	cout << h;
	return 0;
}