TOJ 4284 Happy watering / 贪心

时间限制(普通/Java):1000MS/3000MS     运行内存限制:65536KByte

 

描述

 

 

GBQC国的小明家里有N棵树，每天小明都会给其中一棵树浇水，每次浇水后，树都会长高一些，但由于树的品种不同，每次增长的高度也有所区别。

 

为了使这N棵树看起来整洁、美观，小明希望最高的树和最低的树的高度差越小越好。现在小明想知道，如果至多浇K次水，最高的树和最低的树的高度差最小为多少？

 

 

输入

 

 

输入包含多组测试数据。

 

对于每组测试数据，第一行包含两个正整数N(2<=N<=10^5)、K(1<=K<=10^5)，含义同上。接下来一共有N行，每行有两个正整数h(1<=h<=10^3)、d(1<=d<=10^3)，分别描述了这N棵树的初始高度，以及每次浇水后这棵树增长的高度。

 

输出

 

 

对于每组测试数据，用一行输出一个整数表示如果小明至多浇K次水，最高的树和最低的树的高度差最小为多少。

 

 

样例输入

 

2 1

7 2

10 3

2 4

7 2

10 3

2 3

7 8

10 9

样例输出

 

1

0

3

拿最矮的去浇 贪心

 

优先队列版本

 

 

#include <stdio.h>  
#include <queue>  
using namespace std;  
struct node  
{  
    int current;  
    int h;  
    int k;  
    bool friend operator <(node a,node b)  
    {  
        return a.h > b.h;  
    }  
};  
int main()  
{  
    node x;  
    int n,m,i,max,min;  
    while(scanf("%d %d",&n,&m)!=EOF)  
    {  
        priority_queue<node> q;  
        max = 0;  
        min = 0x7fffffff;  
        for(i = 0;i < n; i++)  
        {  
            scanf("%d %d",&x.h,&x.k);  
            q.push(x);  
            if(max < x.h)  
                max = x.h;  
        }  
        m++;  
        while(m-- && min)  
        {  
            x = q.top();  
            q.pop();  
            int d = max - x.h;  
            if(min > d)  
                min = d;  
            x.h += x.k;  
            if(max < x.h)  
                max = x.h;  
            q.push(x);  
        }  
        printf("%d\n",min);  
    }  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,