MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 230 - Borrowers
AOAPC II

UVaOJ 230 - Borrowers

Chai
2021-11-24 0:00:00在线评测阅读 499

问题描述

p230

原题链接:UVaOJ 230 - Borrowers

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-8

解法一:模拟 + 排序

直接模拟即可,按照题目所属规则排序,排序后的索引可用来建立 title 到对应 id 的映射关系,用来维护信息时快速索引 books[id[title]]. 但需注意到容易 WA 的情况:书架中有多个 title 和 author 相同书籍的情况(此时找到如何/是否能找到前一本书的位置需要好好考虑)。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
 
using namespace std;
 
struct Book {
  string title;
  string author;
  string status;
  bool operator<(const Book &b) const {
    return author < b.author || (author == b.author && title < b.title);
  }
};
 
Book parse_book(string &line) {  // split line into title and author
  Book book;
  int by_pos = line.find(" by ");
  book.title = line.substr(0, by_pos);
  book.author = line.substr(by_pos + 4);
  book.status = "SHELVE";
  return book;
}
 
void do_shelve(vector<Book> &books) {
  for (int i = 0; i < books.size(); ++i)
    if (books[i].status == "RETURN") {
      cout << "Put " << books[i].title;
      int j = i - 1;  // find the previous book (if shelved)
      for (; j >= 0 && books[j].status != "SHELVE"; --j);
      cout << (j < 0 ? " first" : " after " + books[j].title) << endl;
      books[i].status = "SHELVE";
    }
  cout << "END" << endl;
}
 
int main() {
  vector<Book> books;
  string line;
  while (getline(cin, line) && line != "END") books.push_back(parse_book(line));
  sort(books.begin(), books.end());
 
  map<string, int> id;  // title -> id
  for (int i = 0; i < books.size(); i++) id[books[i].title] = i;
 
  while (getline(cin, line) && line != "END") {
    string command = line.substr(0, line.find(" "));
    string title = line.substr(line.find(" ") + 1);
    if (command == "SHELVE") do_shelve(books);
    else books[id[title]].status = command;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz