Skip to content

14211: 【原4211】学者影响力

题目

题目描述

author: Shuhao Li 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4211

Description

H-index(H指数)是一个混合量化指标,可用于评估研究人员的学术产出数量与学术产出水平。H指数是2005年由美国加利福尼亚大学圣地亚哥分校的物理学家乔治·希尔施提出的。通常可以使用H-index来衡量一个学者在某个领域的影响力,Acemap课题组近期完成了对中国计算机学会(CCF)推荐人工智能方向的各个会议做了一个全方位的立体画像,其中使用该指数来衡量机构和作者的影响力指数,并绘制星云图,https://www.acemap.info/ccfgalaxy/author?type=AB_AI_VA 。星云图中可以直观地看出学者和会议直接的影响力大小。

本题提供了一个学者列表,每个学者有一个影响力因子(H-index)。本题要求找到每个学者后方第一个影响力比他大的学者,并输出,如果不存在这样的学者,则输出-1。具体请看输入输出格式说明。

Input Format

第一行一个整数N,表示总共N个学者。

接下来总共N行,每行分别描述第1个到第N个学者信息。每行第一个字段为该学者影响力指数,剩余字段为学者名字(注意名字中可能存在空格)。

Output Format

共输出N行,第i行为第i个学者后方第一个影响力比他大的学者的名字,如果后方找不到影响力指数大于他的,则输出-1。

Sample Input

10
7733 Ronald Allen
105 Tracy Fisher
981 Jeffrey Rodriguez
3355 Benjamin Kerr
76 Michael Rangel
554 Christopher Martinez
419 Dr. Stephanie Brown
2432 Ernest Reed
261 Julie Berry
4433 Jeffrey Reed

Sample Output

-1
Jeffrey Rodriguez
Benjamin Kerr
Jeffrey Reed
Christopher Martinez
Ernest Reed
Ernest Reed
Jeffrey Reed
Jeffrey Reed
-1

Limits

对于 60% 的数据,N <= 5000。

对于 100% 的数据,N <= 500000,名字不超过30个字符。

数据可能存在同名学者。

应当使用栈来实现。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/24.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

template<typename Item>
class Stack {
    class Node {
    public:
        Item val;
        Node *next = nullptr;
    };

    int size;
    Node *top;

public:
    Stack() {
        top = nullptr;
        size = 0;
    }

    void push(const Item &item) {
        top = new Node{item, top};
    }

    Item peek() {
        return top->val;
    }

    Item pop() {
        Node *tmp = top;
        Item ret = top->val;
        top = top->next;
        delete tmp;
        return ret;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    virtual ~Stack() {
        Node *tmp;
        while (top) {
            tmp = top;
            top = top->next;
            delete tmp;
        }
    }
};

class Scholar {
public:
    char name[35];
    int h;
    int kickedBy;

    Scholar(const char *name, int h) {
        strcpy(this->name, name);
        this->h = h;
        kickedBy = -1;
    }
};

int main() {
    int N;
    cin >> N;
    Scholar **scholars = new Scholar *[N];
    Stack<Scholar *> stack;

    char *name = new char[35];
    int h;
    Scholar *tmp;
    for (int i = 0; i < N; ++i) {
        scanf("%d", &h);
        fgets(name, 35, stdin);
        scholars[i] = new Scholar(name + 1, h);

        if (stack.isEmpty()) {
            stack.push(scholars[i]);
        } else {
            while (!stack.isEmpty()) {
                if (stack.peek()->h < h) {
                    stack.pop()->kickedBy = i;
                } else {
                    break;
                }
            }
            stack.push(scholars[i]);
        }
    }

    for (int i = 0; i < N; ++i) {
        if (scholars[i]->kickedBy == -1) {
            printf("-1");
        } else {
            printf(scholars[scholars[i]->kickedBy]->name);
        }
        printf("\n");
    }
    return 0;
}

ligongzzz's solution

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

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

    int n;
    cin >> n;

    vector<string> ans(n, "-1");
    stack<pair<int, pair<int, string>>> sdata;

    for (int i = 0; i < n; ++i) {
        int val;
        string name;
        cin >> val;
        cin.get();
        getline(cin, name);

        for (; !sdata.empty() && val > sdata.top().second.first;) {
            ans[sdata.top().first] = name;
            sdata.pop();
        }
        sdata.push(make_pair(i, make_pair(val, name)));
    }

    for (auto& p : ans)
        cout << p << "\n";
    return 0;
}

skyzh's solution

#include <cstdio>
using namespace std;

char name[500000][31];
int influence[500000];
int result[500000];
int s[500000], top = 0;
int N;

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d ", &influence[i]);
        fgets(name[i], 31, stdin);
    }
    for (int i = 0; i < N; i++) {
        if (top == 0) result[i] = -1;
        else {
            while (top > 0) {
                int _t = s[top - 1];
                if (influence[i] > influence[_t]) {
                    result[_t] = i;
                    --top;
                } else break;
            }
        }
        s[top++] = i;
    }
    while (top > 0) {
        --top;
        result[s[top]] = -1;
    }
    for (int i = 0; i < N; i++) {
        if (result[i] != -1) {
            fputs(name[result[i]], stdout);
        } else {
            fputs("-1\n", stdout);
        }
    }
    return 0;
}