砍树问题

Time Limit : 3000/1000ms (Java/Other) Memory Limit :

65535/32768K(Java/Other)

Total Submission(s) : 282 Accepted Submission(s): 44

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

ProblemDescription

自从周正虎被告知山上并没有老虎后就成为了当地一名伐木工人。这一次他需要砍下M

米的木材，当然，自从有了新的伐木工具之后，这对他来说简直就是一件轻而易举的事

情。

周正虎的伐木工具的使用说明书上这样写道：机器需要设定一个高度参数H（米），然后

机器就会升高到H（米），砍下所有高于H（米）的树。对于高度没有达到H（米）的树，

我们认为它是幸运的，在这次砍伐中它将免受威胁。例如：现有树的高度为20, 15, 10,

17 将机器设置为15，那么我们将砍伐到第一和第四棵树，得到的木材长度为(20-15) +

(17-15) = 7。

周正虎是一个爱好环境的人，所以他想知道他最高能将机器的高度设置为多少去满足至

少砍下M 米的木材。

Input

输入有多组数据。第一行将输入两个数据，1 <= N <= 1 000 000，1<= M <= 2 000

000 000分别代表树的棵树以及要得到的木材的长度，

第二行将包含以空格隔开的N 个数，分别表示第1到第N 棵树的高度。每棵树的高度小

于1 000 000 000，树的高度总和将超过M，周正虎将始终得到他想要的木材长度。

Output

输出有且仅有一行，表示要求输出的高度。

Sample Input

4 7

20 15 10 17

5 20

4 42 40 26 46

SampleOutput

15

36

思路：

现将所给的数组排序用sort排序后，比如高度分别为 20 17 15 10

第一次，以17砍，看后发现比要砍得少了，那就再以15砍，若果多了就停止下降高度，少了就继续下降，当多了时，再用h=砍时的高度+（现在砍下来的-要砍得）/(砍得树的棵树)；输出即可

#include

#include

#include

using namespace std;

#define N 1000010

int a[N];

int cmp(int a,int b){

return a>b;

}

int main(){

int n,m,i,c,sum;

while(cin>>n>>m)

{

for(i=0;iscanf(\"%d\",&a[i]);

sort(a,a+n,cmp);

for(i=0,c=1;i{

sum+=c*(a[i]-a[i+1]);

if(sum>=m)

break;

}

h=a[i+1]+(sum-m)/c;

printf(\"%d\\n\",h);

}

return 0;

}