14205: 【原4205】Turing Award
题目
题目描述
author: Shuhao Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4205
Description
图灵奖（英语：ACM A.M. Turing Award），又译杜林奖、A.M.图灵奖，是计算机协会（ACM）于1966年设立的奖项，专门奖励对计算机事业作出重要贡献的个人。其名称取自世界计算机科学的先驱、英国科学家、曼彻斯特大学教授艾伦·图灵（A.M. Turing），这个奖设立目的之一是纪念这位现代计算机科学的奠基者。获奖者必须是在计算机领域具有持久而重大的先进性的技术贡献。大多数获奖者是计算机科学家。是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。
图灵奖开设至今已经有50余载，其中出了不少图灵奖得主，Acemap课题组在图灵奖50周年的时候制作了一个关于图灵奖得主以及其相关合作者的可视化关系图，https://acemap.cn/turing50 （使用Google Chrome浏览器打开可以达到最佳浏览效果），可供参考。
本题要求维护一个链表，链表提供插入，删除，索引等操作。链表中储存了图灵奖得主的获奖年份和名字。要求按照获奖年份从小到大排序，如果两个得主获奖年份一致，则按照名字的字典序从小到大排序。具体要求见下方输入输出格式说明。
Input Format
第一行一个整数N，表示总共的操作次数。
接下来总共N行，每行执行一个操作。
每行的第一个字段指示操作的类型，分别有insert, delete, list三种不同的操作，格式如下。
如果第一个字段是insert，则第二个字段为该图灵得主的获奖年份，剩余字段为图灵得主的名字（注意名字中可能有空格）。程序执行插入操作，将该得主插入链表中，并且保持得奖年份从小到大的顺序排列（如果有两个得主的年份一致，则按照其名字的字典序从小到大的顺序）。
如果第一个字段是delete，则第二个字段是一个正整数i，表示删除链表中第i个结点（从1开始算，不从0开始）。
如果第一个字段是list，则第二个字段是一个正整数i，表示打印出第i个结点（从1开始算，不从0开始）的图灵得主的获奖年份和名字。中间用一个空格隔开。
Output Format
对于每个list操作，输出一行，表示相对应图灵得主的获奖年份和名字，中间用一个空格隔开。
Sample Input
10
insert 1982 Stephen A. Cook
insert 2002 Adi Shamir
list 1
list 2
delete 2
insert 2014 Michael Stonebraker
insert 2004 Robert E. Kahn
list 3
delete 1
list 1
Sample Output
1982 Stephen A. Cook
2002 Adi Shamir
2014 Michael Stonebraker
2004 Robert E. Kahn
Limits
对于100%的数据，名字不超过30个字符，N <= 3000。
数据保证所有操作都合法，不会出现越界的情况。
应当使用链表来实现，不使用链表得0分。
BugenZhao's solution
//
// Created by BugenZhao on 2019/3/16.
//
// 链表基本练习
#include <iostream>
#include <string>
using namespace std;
class TuringAwardWinnerLinkedList {
class Node {
public:
int year = 0;
string name;
Node *next = nullptr;
};
static inline bool less(const Node &a, const Node &b) {
return a.year == b.year ? a.name < b.name : a.year < b.year;
}
Node *head;
int size;
public:
TuringAwardWinnerLinkedList() {
size = 0;
head = new Node{0, "666", nullptr};
}
void insert(int year, const string &name) {
Node *toInsert = new Node{year, name, nullptr};
Node *p = head;
while (p != nullptr) {
if (p->next == nullptr) {
p->next = toInsert;
break;
}
if (less(*toInsert, *p->next)) {
Node *tmp = p->next;
p->next = toInsert;
toInsert->next = tmp;
break;
}
p = p->next;
}
++size;
}
void del(int i) {
i -= 1;
Node *p = head;
while (i--) {
p = p->next;
}
Node *tmp = p->next;
p->next = tmp->next;
delete tmp;
--size;
}
void list(int i) {
Node *p = head;
while (i--) {
p = p->next;
}
cout << p->year << " " << p->name << endl;
}
virtual ~TuringAwardWinnerLinkedList() {
Node *p = head->next;
while (p != nullptr) {
Node *tmp = p->next;
delete p;
p = tmp;
}
delete head;
}
};
int main() {
TuringAwardWinnerLinkedList linkedList;
int N;
string op;
cin >> N;
while (N--) {
cin >> op;
if (op == "insert") {
int year;
string name;
cin >> year;
getline(cin, name);
linkedList.insert(year, name.substr(1, name.size() - 1));
} else if (op == "delete") {
int i;
cin >> i;
linkedList.del(i);
} else if (op == "list") {
int i;
cin >> i;
linkedList.list(i);
}
}
return 0;
}
skyzh's solution
#include <iostream>
#include <cstring>
using namespace std;
class LinkedList {
public:
struct Node {
int yrs;
char name[40];
Node* next;
} *head;
LinkedList() {
head = new Node;
head->yrs = 0;
head->next = NULL;
}
Node* list(int i) const {
Node* ptr = head;
while (i > 0) {
--i;
ptr = ptr->next;
}
return ptr;
}
void insert(Node* data) {
Node* ptr = head->next, *prev = head;
while (ptr &&
(ptr->yrs < data->yrs ||
(ptr->yrs == data->yrs) && strcmp(ptr->name, data->name) < 0)) {
prev = ptr;
ptr = ptr->next;
}
prev->next = data;
data->next = ptr;
}
void del(int i) {
Node* ptr = head;
while (i > 1) {
--i;
ptr = ptr->next;
}
Node *tmp = ptr->next;
ptr->next = tmp->next;
delete tmp;
}
~LinkedList() {
Node* ptr = head;
while (ptr) {
Node* next = ptr->next;
delete ptr;
ptr = next;
}
}
};
int main() {
LinkedList lst;
char cmd[100];
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> cmd;
if (strcmp(cmd, "insert") == 0) {
LinkedList::Node* ptr = new LinkedList::Node;
ptr->next = NULL;
cin >> ptr->yrs;
cin.getline(ptr->name, 40);
lst.insert(ptr);
} else if (strcmp(cmd, "delete") == 0) {
int cnt;
cin >> cnt;
lst.del(cnt);
} else if (strcmp(cmd, "list") == 0) {
int cnt;
cin >> cnt;
LinkedList::Node* ptr = lst.list(cnt);
cout << ptr->yrs << " " << ptr->name << endl;
}
}
return 0;
}