14229: 【原4229】Paper Citation

题目

题目描述

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

Description

一篇论文的被引用数是衡量一篇论文价值的重要指标，论文的引用数通常会随着时间的增加而增加。现在有n篇论文，编号从0～n-1，本题给出一个论文引用序列，要求针对每一个询问，输出当前被引用数最高的论文编号以及其当前的被引用数。

Input Format

第一行一个整数N，表示总共的论文数目，从0～n-1编号。

接下来若干行，每行执行一个操作。

每行的第一个字段指示操作的类型，分别有add, query, finish三种不同的操作，格式如下。

如果第一个字段是add，则接下来输入两个整数i，j 表示论文i引用的论文j，也就是说论文j的被引用数增加1。

如果第一个字段是query，则输出当前论文被引用数最高的论文编号和被引用数，用空格隔开，如果有两篇以上的论文符合条件，输出论文编号最小的那一个。

如果第一个字段是finish，则结束输入。

请注意，该题中的测试数据中会存在重复引用和循环引用的情况，这在实际情况中是不存在的。但不影响解题的结果，重复引用也重复计算被引用次数。

Output Format

对于每个query操作，输出一行，包括两个整数，表示引用量最高的论文编号和引用量，中间用一个空格隔开。

Sample Input

3
add 1 2
query
add 3 1
add 2 1
query
add 3 2
add 1 2
query
finish

Sample Output

2 1
1 2
2 3

Limits

对于100%的数据，N <= 50000，总操作数不大于1000000。

BugenZhao's solution

//
// Created by BugenZhao on 2019/4/29.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    auto counts = new int[N + 1]{};
    int maxPos = 0;
    int maxCount = 0;

    string cmd;
    int a, b;
    while (true) {
        cin >> cmd;
        if (cmd[0] == 'f') break;
        else if (cmd[0] == 'a') {
            cin >> a >> b;
            ++counts[b];
            if (counts[b] == maxCount) {
                maxPos = maxPos < b ? maxPos : b;
            } else if (counts[b] == maxCount + 1) {
                maxCount += 1;
                maxPos = b;
            }
        } else if (cmd[0] == 'q') {
            cout << maxPos << ' ' << maxCount << '\n';
        }
    }

    delete[] counts;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int val_num[50009] = { 0 };

int main() {
    int n;
    scanf("%d", &n);

    int cur_max = 0, max_n = 0;
    while (true) {
        char op[10];
        scanf("%s", op);
        if (strcmp(op, "add") == 0) {
            int a, b;
            scanf("%d %d", &a, &b);
            ++val_num[b];
            if (val_num[b] == max_n) {
                if (b < cur_max) {
                    cur_max = b;
                }
            }
            if (val_num[b] > max_n) {
                cur_max = b;
                max_n = val_num[b];
            }
        }
        else if (strcmp(op, "query") == 0) {
            printf("%d %d\n", cur_max, max_n);
        }
        else {
            break;
        }
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>

using namespace std;

int ref_cnt[250001] = {0};

inline char get_cmd() {
    char ch;
    while (ch = getchar()) {
        if ('a' <= ch && ch <= 'z') return ch;
    }
}

inline int get_int() {
    int x = 0;
    char ch;
    while (ch = getchar()) {
        if ('0' <= ch && ch <= '9') break;
    }
    do {
        if ('0' <= ch && ch <= '9') {
            x = x * 10 + (ch - '0');
        } else break;
    } while (ch = getchar());
    return x;
}

int main() {
    int n;
    n = get_int();
    char cmd;
    int op1, op2;
    int cur_max = 0, cur_max_idx = 0;
    while (true) {
        cmd = get_cmd();
        switch (cmd) {
            case 'a':
                op1 = get_int();
                op2 = get_int();
                ++ref_cnt[op2];
                if (ref_cnt[op2] > cur_max || ref_cnt[op2] == cur_max && op2 < cur_max_idx) {
                    cur_max = ref_cnt[op2];
                    cur_max_idx = op2;
                }
                break;
            case 'f':
                return 0;
            case 'q':
                printf("%d %d\n", cur_max_idx, cur_max);
                break;
        }
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <iostream>
#define MAX_N 50010
int n, cur_max_id, x;
int a[MAX_N];
char op;
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
int main() {
    n = read();
    op = getchar();
    while (op != 'f') {
        if (op == 'q') {
            printf("%d %d\n", cur_max_id, a[cur_max_id]);
            while (op != '\n') op = getchar();
        }
        else if (op == 'a') {
            read(); x = read();
            ++a[x];
            if (a[x] > a[cur_max_id] || a[x] == a[cur_max_id] && x < cur_max_id) {
                cur_max_id = x;
            }
        }
        op = getchar();
    }
    return 0;
}