Problem 1921 栀子花开
Accept: 323 Submit: 1156
Time Limit: 1000 mSec Memory Limit : 32768
KB
Problem Description
这是一个栀子花开的季节，也是一个离别的季节，四年一千多个日日夜夜，那校园的角角落落，留下了我们沉思的身影；那上百次的成绩排名表，印证了我们深深浅浅不断进步的轨迹，但是这些进步都离不开老师的谆谆教诲。
作为计算机系的学生，算法与数据结构是必修的主干课程，因此课程的每个老师都很关心每个学生的学习情况，每天下课老师都会给某个学生进行课外辅导。首先，老师会给每个学生一个能力评定分数，如果有学生要求老师给他辅导，那老师就会专门给该同学进行课外辅导，如果没有学生要求，老师就会给评定分数最低的同学课外辅导。老师给学生辅导后，学生的能力都会有所增长，然而不同的学生增长的情况都不同。老师想知道为学生课外辅导若干天后，全班的最低分学生的编号和分数。
Input
首先第一行为T，表示有T组数据。接下来为每组数据的结构：
第一行有一个数字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
对于每组数据输出一行先输出组数(从1开始)，接着最后输出经过m天后，全班的最低分学生的编号和分数。
Sample Input
1
3
10 20 30
3
0 100
3 10
0 40
Sample Output
Case 1: 3 40
Hint
上面的数据，各个学生的能力增长情况如下：
第一天后：110 20 30
第二天后：110 20 40
第三天后：110 60 40
Source
FOJ有奖月赛-2010年06月 并不明白这个程序哪有错……
1 #include "bits/stdc++.h" 2 #define mem(a,b) memset(a,b,sizeof(a)) 3 #define lson rt<<1,l,m 4 #define rson rt<<1|1,m+1,r 5 using namespace std; 6 typedef long long LL; 7 const int MAX=100005; 8 int T; 9 int n,m; 10 int c[MAX*8],ans; 11 int pos[MAX],tot; 12 void PushUp(int rt){ 13 c[rt]=min(c[rt<<1],c[rt<<1|1]); 14 } 15 void build(int rt,int l,int r){ 16 if (l==r){ 17 pos[++tot]=rt; 18 scanf("%d",&c[rt]); 19 return; 20 } 21 int m=(l+r)>>1; 22 build(lson); 23 build(rson); 24 PushUp(rt); 25 } 26 void update1(int rt,int l,int r,int x,int y){ 27 if (l==r){ 28 c[rt]+=y; 29 return; 30 } 31 int m=(l+r)>>1; 32 if (x<=m) 33 update1(lson,x,y); 34 else 35 update1(rson,x,y); 36 PushUp(rt); 37 } 38 void update2(int rt,int l,int r,int y){ 39 if (l==r){ 40 c[rt]+=y; 41 return; 42 } 43 int m=(l+r)>>1; 44 if (c[rt<<1]<=c[rt<<1|1]) 45 update2(lson,y); 46 else 47 update2(rson,y); 48 PushUp(rt); 49 } 50 int main(){ 51 freopen ("flower.in","r",stdin); 52 freopen ("flower.out","w",stdout); 53 int i,j,cas(0); 54 int x,y; 55 scanf("%d",&T); 56 while (T--){ 57 scanf("%d",&n); 58 build(1,1,n); 59 scanf("%d",&m); 60 for (i=1;i<=m;i++){ 61 scanf("%d%d",&x,&y); 62 if (x==0) 63 update2(1,1,n,y); 64 else 65 update1(1,1,n,x,y); 66 } 67 ans=1; 68 for (i=2;i<=n;i++) 69 if (c[pos[ans]]>c[pos[i]]) 70 ans=i; 71 printf("Case %d: %d %d ",++cas,ans,c[pos[ans]]); 72 } 73 return 0; 74 }