本文主要是介绍【FZU】1921 栀子花开 线段树果题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem 1921 栀子花开Accept: 216 Submit: 745
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
作为计算机系的学生，算法与数据结构是必修的主干课程，因此课程的每个老师都很关心每个学生的学习情况，每天下课老师都会给某个学生进行课外辅导。首先，老师会给每个学生一个能力评定分数，如果有学生要求老师给他辅导，那老师就会专门给该同学进行课外辅导，如果没有学生要求，老师就会给评定分数最低的同学课外辅导。老师给学生辅导后，学生的能力都会有所增长，然而不同的学生增长的情况都不同。老师想知道为学生课外辅导若干天后，全班的最低分学生的编号和分数。
Input
第一行有一个数字n，表示有n个学生，编号从1到n。(1 <= n <= 10000)。
接下来一行有n个数，分别是编号从1到n的学生的初始能力水平xi，(1 <= xi <= 1000)。
接下来有一行有一个数m表示老师给学生课外辅导了m天(1 <= m <= 100000)。
接下来m行，每行两个数(ai bi)，表示老师在第i天给编号为ai同学补课，编号为ai的同学能力提高了bi(0 <= ai <= n,1 <= bi <= 1000)。如果ai为0，则表示老师今天给能力最差的学生辅导。如果最低分同时有多个学生，就给编号小的学生补课。
Output
Sample Input
Sample Output
Hint
上面的数据，各个学生的能力增长情况如下：第一天后：110 20 30
第二天后：110 20 40
第三天后：110 60 40
Source
FOJ有奖月赛-2010年06月传送门：【FZU】1921 栀子花开
题目分析：不多说，线段树果题，维护区间最小，相同最小往左儿子身上走。
不知道是不是我没看清题意
，你说输出的时候要是有相同最小的我该怎么输出
。。。反正我不管了，就输出最左端的。。。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;typedef long long Int ;#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define rt l , r , o
#define root 1 , n , 1
#define lson l , m , ls
#define rson m + 1 , r , rs
#define mid ( ( l + r ) >> 1 )
#define clear( A , X ) memset ( A , X , sizeof A )const int maxN = 10005 ;
const int oo = 0x3f3f3f3f ;int mmin[maxN << 2] ;int min ( const int X , const int Y ) {if ( X < Y ) return X ;return Y ;
}void PushUp ( int o ) {mmin[o] = min ( mmin[ls] , mmin[rs] ) ;
}void Build ( int l , int r , int o ) {if ( l == r ) {scanf ( "%d" , &mmin[o] ) ;return ;}int m = mid ;Build ( lson ) ;Build ( rson ) ;PushUp ( o ) ;
}void Update ( int pos , int val , int l , int r , int o ) {if ( l == r ) {mmin[o] += val ;return ;}int m = mid ;if ( !pos ) {if ( mmin[ls] <= mmin[rs] ) Update ( pos , val , lson ) ;else Update ( pos , val , rson ) ;}else{if ( pos <= m ) Update ( pos , val , lson ) ;else Update ( pos , val , rson ) ;}PushUp ( o ) ;
}void Query ( int l , int r , int o ) {if ( l == r ) {printf ( "%d %d\n" , l , mmin[o] ) ;return ;}int m = mid ;if ( mmin[ls] <= mmin[rs] ) Query ( lson ) ;else Query ( rson ) ;
}void work () {int n , m , x , v ;scanf ( "%d" , &n ) ;Build ( root ) ;scanf ( "%d" , &m ) ;while ( m -- ) {scanf ( "%d%d" , &x , &v ) ;Update ( x , v , root ) ;}Query ( root ) ;
}
int main () {int T , cas ;for ( scanf ( "%d" , &T ) , cas = 1 ; cas <= T ; ++ cas ) {printf ( "Case %d: " , cas ) ;work () ;}return 0 ;
}
这篇关于【FZU】1921 栀子花开 线段树果题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
