Skip to content

11128: 【原1128】神奇的篮筐

题目

题目描述

author: Xiaoyang Lin 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1128

Description

Super.Y最近很伤心,因为他的好球友一鸣受伤了,这样就没人陪Super.Y打球了。所以Super.Y只能自己去练投篮了。

场地上有N个篮筐,球投进第i个篮筐可以得到Di分且投进后这个篮筐就消失了,神奇的是,第i个篮筐会在第Ti秒末消失。(即要么被投消失,要么在Ti秒末消失)

Super.Y的命中率为100%,他一秒中可以投进一个球,他想知道他最多能得到多少分.

P.S:以此祝愿一鸣早日康复

Input Format

一行,两个空格隔开的整数A,B。

Output Format

第1行:N

第2~N+1行 Di Ti

Sample Input

3
1 2
2 2
3 1

Sample Output

5

Limits

60% 1<=N <=1000

100% 1<=N<=100000,1<=Di,Ti<=10000

ligongzzz's solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<pair<int, int>> vector_data(n);

    for (int i = 0; i < n; ++i) {
        cin >> vector_data[i].first >> vector_data[i].second;
    }

    sort(vector_data.begin(), vector_data.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second; });

    int ans = 0;
    priority_queue<int> queue_data;
    for (int t = vector_data.front().second, i = 0; t > 0; --t) {
        for (; i < vector_data.size() && vector_data[i].second >= t; ++i)
            queue_data.push(vector_data[i].first);
        if (!queue_data.empty()) {
            ans += queue_data.top();
            queue_data.pop();
        }
    }

    cout << ans;

    return 0;
}

yyong119's solution

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX_N 100010
using namespace std;

struct node{
    int d, t;
}a[MAX_N];
int n, ans;
int sum[MAX_N];

inline bool cmp(node p, node q) {
    return p.t > q.t;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].d, &a[i].t);
    sort(a, a + n, cmp);
    priority_queue<int, vector<int>, less<int> > que;
    int idx = 0;
    for (int t_end = a[0].t - 1; t_end >= 0; --t_end) {
        while(a[idx].t > t_end && idx < n)
            que.push(a[idx++].d);
        if (!que.empty()) {
            ans += que.top();
            que.pop();
        }
    }
    printf("%d\n", ans);
    return 0;
}