# 11113: 【原1113】二哥的奖学金

### 题目描述

author: Cheng Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1113

## Sample Input

``````3 5 70
30 25
50 21
20 20
5 18
35 30
``````

## Sample Output

``````35
``````

## FineArtz's solution

``````/* 二哥的奖学金 */
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 2000000005;

class Heap{
private:
int a[200005] = {0};
int heapsize = 0;

void swap(int x, int y){
int t = a[x];
a[x] = a[y];
a[y] = t;
}

void siftup(int i){
while (i != 1){
if (a[i] > a[i / 2]){
swap(i, i / 2);
i /= 2;
}
else
break;
}
}

void siftdown(){
int i = 2;
while (i <= heapsize){
if (i + 1 <= heapsize && a[i] < a[i + 1])
++i;
if (a[i / 2] < a[i]){
swap(i, i / 2);
i *= 2;
}
else
break;
}
}

public:
void insert(int x){
a[++heapsize] = x;
siftup(heapsize);
}

void remove(){
swap(1, heapsize);
--heapsize;
siftdown();
}

int getMax(){
return a[1];
}

void removeAndInsert(int x){
a[1] = x;
siftdown();
}
};

pair<int, int> a[200005];
int sum1[200005] = {0}, sum2[200005] = {0};
int n, c, f;
Heap heap1, heap2;

void qsort(int l, int h){
if (l >= h)
return;
int i = l, j = h;
pair<int, int> key = a[l];
while (i < j){
while (i < j && a[j] > key)
--j;
a[i] = a[j];
while (i < j && a[i] < key)
++i;
a[j] = a[i];
}
a[i] = key;
qsort(l, i - 1);
qsort(i + 1, h);
}

int main(){
cin >> n >> c >> f;
for (int i = 1; i <= c; ++i){
cin >> a[i].first >> a[i].second;
}
sort(a + 1, a + c + 1);
//    for (int i = 1; i <= c; ++i)
//        cout << a[i].first << ' ' << a[i].second << endl;
for (int i = 1; i <= n / 2; ++i){
sum1[n / 2] += a[i].second;
heap1.insert(a[i].second);
}
for (int i = n / 2 + 1; i <= c; ++i){
int t = a[i].second;
if (t > heap1.getMax())
sum1[i] = sum1[i - 1];
else{
sum1[i] = sum1[i - 1] - heap1.getMax() + t;
heap1.remove();
heap1.insert(t);
}
}
for (int i = c; i >= c - n / 2 + 1; --i){
sum2[c - n / 2 + 1] += a[i].second;
heap2.insert(a[i].second);
}
for (int i = c - n / 2; i >= 1; --i){
int t = a[i].second;
if (t > heap2.getMax())
sum2[i] = sum2[i + 1];
else{
sum2[i] = sum2[i + 1] - heap2.getMax() + t;
heap2.remove();
heap2.insert(t);
}
}
int ans = -1;
for (int i = n / 2 + 1; i <= c - n / 2; ++i){
int t = sum1[i - 1] + sum2[i + 1] + a[i].second;
if (t <= f && ans < a[i].first)
ans = a[i].first;
}
cout << ans << endl;
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <algorithm>
#include <iostream>
#define MAX_C 100010
#define RG register
using namespace std;
struct Node {
int grd, sch;
} a[MAX_C];
int n, c, f, half;
int sum_left[MAX_C], sum_right[MAX_C], max_heap[MAX_C];
char ch = getchar(); int flag = 1, res = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}
inline bool cmp_grd(const Node& a, const Node& b) {
return a.grd < b.grd;
}
inline bool cmp_sch(const Node& a, const Node& b) {
return a.sch < b.sch;
}
int main() {
half = n >> 1;// numbers that two side of center number need
for (RG int i = 0; i < c; ++i)
sort(a, a + c, cmp_grd);
// calc minimum sum of the left part
for (RG int i = 0; i < half; ++i) {
max_heap[i] = a[i].sch;
sum_left[half - 1] += a[i].sch;
}
make_heap(max_heap, max_heap + half, less<int>());
for (RG int i = half; i < c; ++i) {
sum_left[i] = sum_left[i - 1];
if (a[i].sch < max_heap[0]) {
sum_left[i] -= max_heap[0];
sum_left[i] += a[i].sch;
pop_heap(max_heap, max_heap + half, less<int>());
max_heap[half - 1] = a[i].sch;
push_heap(max_heap, max_heap + half, less<int>());
}
}
// calc minimum sum of the right part
for (RG int i = c - 1; i >= c - half; --i) {
max_heap[c - i - 1] = a[i].sch;
sum_right[c - half] += a[i].sch;
}
make_heap(max_heap, max_heap + half, less<int>());
for (RG int i = c - half - 1; i >= 0; --i) {
sum_right[i] = sum_right[i + 1];
if (a[i].sch < max_heap[0]) {
sum_right[i] -= max_heap[0];
sum_right[i] += a[i].sch;
pop_heap(max_heap, max_heap + half, less<int>());
max_heap[half - 1] = a[i].sch;
push_heap(max_heap, max_heap + half, less<int>());
}
}
// enumerate each center number
for (RG int i = c - half - 1; i >= half; --i)
if (sum_left[i - 1] + sum_right[i + 1] + a[i].sch <= f) {
printf("%d\n", a[i].grd);
return 0;
}
printf("-1\n");
return 0;
}
``````