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

题目描述

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

Description

二哥发表论文后，有一个神秘人物要为二哥的学校发奖学金。二哥的学校有C名学生，要从中挑出N个。这个神秘人物的爱好比较奇特，他希望得到奖学金的同学的成绩的中位数尽量大。但同时，他们的奖学金总额不能超过F。

Input Format

第一行整数是N、C和F。N一定是奇数，N <= C，0 <=F<= 2000000000，N<=100000，C<=20000。接下来的C行，每行描述一名学生的成绩和奖学金。0<=成绩<=2000000000；0 <=奖学金<=100000。

Output Format

满足条件的最大中位数。如果无解，输出-1。

Sample Input

Sample Output

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];
inline int read() {
    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() {
    n = read(); c = read(); f = read();
    half = n >> 1;// numbers that two side of center number need
    for (RG int i = 0; i < c; ++i)
        a[i].grd = read(), a[i].sch = read();
    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;
}