Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一个过的方法(一堆二用)

Posted by 3250 at 2009-05-10 10:49:21 on Problem 2010
// 记录牛学生的数组
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator