Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一个过的方法(一堆二用)// 记录牛学生的数组 struct Cow{ int score,aid; int up,down; }c[100001]; int h[10001]; 先以score排序(顺序逆序个人爱好),(假设c数组0开始从左到右) 1、存最左边的n/2个c的aid值到h数组,对h构造最大堆(nlogn),从n/2+1开始到C-n/2的c中,依次替换h中最大的数(Clogn),并且update数组h的总和,这个总和,记录在相应的c的up中,表示比这个学生高分(或者低分)的n/2个学生的最小和。 2、同理,存最右边的n/2个c的aid值到h数组,对h构造最大堆(nlogn),从C-n/2开始到n/2+1的c中,依次替换h中最大的数(Clogn),并且update数组h的总和,这个总和,记录在相应的c的down中,表示比这个学生高分(或者低分)的n/2个学生的最小和。 从n/2+1开始到C-n/2扫一遍,将sum=c[i].up+c[i].aid+c[i].down中符合条件,且i最小(或者最大)的score记下来,printf之。 (2Clogn) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator