学步园

1098: Happy watering

Time Limit: 1 Sec  Memory Limit: 16 MB
SUBMIT: 42  Solved: 20

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1098

Description

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

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

Input

输入包含多组测试数据。

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

Output

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

Sample Input

2 1 7 2 10 3 2 4 7 2 10 3 2 3 7 8 10 9 

Sample Output

1 0 3 

HINT

    由于数据量较大，推荐使用scanf和printf。

Source

CSU Monthly 2012 Aug.

线段树解题，单点更新

题目求最高的树和最低的树的最小高度差，那么每次帮最低的树浇水，以减少高度差，当然，有可能增加高度差，但这是减小高度差的惟一方法了，有2个数组，一个保存区域内的最小值，另一个保存区域内的最大值，每浇一次水，更新结点，并计算高度差，若比原来的最小高度差小，则更新最小高度差

这个题一开始思路是对的，结果线段树的代码写错了一步，导致TLE，这个结果让我很奇怪，一般10^5是不会超的，用线段数好像10^6的题都做过，最后终于发现有一步没判断就执行了，结果导致了很多多余的计算，但不会导致结果错误0.0

可能是很久没写线段树了。。。。。

#include<stdio.h>
#define MAXN 100000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
  
int num[MAXN<<2][3];
  
void PushUp(int rt)
{
    num[rt][0]=num[rt<<1][0]<num[rt<<1|1][0]?num[rt<<1][0]:num[rt<<1|1][0];
    num[rt][1]=num[rt<<1][1]>num[rt<<1|1][1]?num[rt<<1][1]:num[rt<<1|1][1];
}
  
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d%d",&num[rt][0],&num[rt][2]);
        num[rt][1]=num[rt][0];
//      printf("%d %d\n",rt,num[rt][0]);
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
//  printf("%d %d\n",rt,num[rt][0]);
}
  
void fun(int tmp,int l,int r,int rt)
{
    if(l==r)
    {
        if(num[rt][0]==tmp)
        {
            num[rt][0]+=num[rt][2];
            num[rt][1]+=num[rt][2];
//          printf("%d %d\n",rt,num[rt][0]);
        }
        return ;
    }
    int m=(l+r)>>1;
    if(tmp==num[rt<<1][0])           //这里开始忘记判断了，结果很悲剧。。。。。
        fun(tmp,lson);
    else
        fun(tmp,rson);
    PushUp(rt);
//  printf("%d %d\n",rt,num[rt][0]);
}
  
int main(void)
{
    int N,K;
 // freopen("d:\\in.txt","r",stdin);
    while(scanf("%d%d",&N,&K)==2)
    {
        build(1,N,1);
        int i,min=num[1][1]-num[1][0];
        for(i=1;i<=K;i++)
        {
            fun(num[1][0],1,N,1);
            if(num[1][1]-num[1][0]<min)
                min=num[1][1]-num[1][0];
            if(min==0)
                break;
        }
        printf("%d\n",min);
    }
    return 0;
}
/**************************************************************
　　Language: C++
　　Time:236 ms
    Memory:5476 kb
****************************************************************/