小美的书架 #

发布于2021-04-16

上次编辑2021-04-16

问题描述#

小美的书架上有很多书。小美是个爱读书的新时代好青年。
小团虽然也喜欢看书，但小团大多数时候都更喜欢来小美家蹭书读。
这就导致小美的书架上很多书都会被小团借走。
小美很烦这一点，就想出了一个招数，小美的书架是一行一行的，他会对一些行加锁，这样小团就借不走了。
现在小团想要借书，请你帮忙看看小团能不能借到书，如果可以借到的话在哪一行书架上有这本书。
为了简单起见，每本书将用一个正整数进行编号，小美的书架一共有 N 行。

格式：
输入：
- 第一行两个正整数 N，M，Q，表示小美书架有 N 行编号 1 到 N ，书本编号从 1 到 M ，接下来有 Q 个操作
- 接下来 Q 行，每行是下列操作中的一种：
  1. x y : x 是书本的编号，y 是书架的行编号，代表小美将编号为 x 的书本放置到 y 行上。若该书本在小团手上则放置无效，若原来该书在书架上且原行上锁则放置无效，若该书被放置到一个锁了的行上则放置无效。
  2. y : y 是书架的行编号，代表小美将行编号为 y 的书架加锁，对已经上锁的书架行该操作无效。
  3. y : y 是书架的行编号，代表小美将行编号为 y 的书架锁去掉，对无锁的书架行该操作无效。
  4. x : x 是书本的编号，代表小团想借编号为 x 的书本，对该操作若可以借到输出一行正整数在哪一行，借不到输出一行 -1
  5. x : x 是书本的编号，代表小团还回来编号为 x 的书本。若该书本不在小团手上该操作无效。
输出：
- 对于每个操作 4 ，若可以借到输出一行正整数在哪一行，借不到输出一行 -1 。
示例：
输入：
     5 5 10
     1 1 4
     1 2 3
     1 3 1
     2 1
     4 1
     5 2
     4 3
     4 5
     3 1
     4 2
输出：
     4
     -1
     -1
     3
提示：

对于 30% 的数据有 N<=10, M<=10, Q<=20

对于 80% 的数据有 N<=1000, M<=1000, Q<=100000

对于 100% 的数据有 N<=10000, M<=10000, Q<=100000

解题思路#

Python

import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


N, M, Q = readints()
row = [False] * 10005
book = [0] * 10005
for _ in range(Q):
    A = readints()
    k = A[0]
    if k == 1:
        x, y = A[1], A[2]
        if book[x] != -1 and not row[y] and (book[x] == 0 or not row[book[x]]):
            book[x] = y
    elif k == 2:
        y = A[1]
        row[y] = True
    elif k == 3:
        y = A[1]
        row[y] = False
    elif k == 4:
        x = A[1]
        if book[x] > 0 and not row[book[x]]:
            print(book[x])
            book[x] = -1
        else:
            print(-1)
    else:
        x = A[1]
        if book[x] == -1:
            book[x] = 0

C++

#include <bits/stdc++.h>
using namespace std;
int book[10005];
bool row[10005];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int N, M, Q;
    cin >> N >> M >> Q;
    while (Q--) {
        int k, x, y;
        cin >> k;
        if (k == 1) {
            cin >> x >> y;
            if (book[x] != -1 && !row[y] && (!book[x] || !row[book[x]])) {
                book[x] = y;
            }
        } else if (k == 2) {
            cin >> y;
            row[y] = 1;
        } else if (k == 3) {
            cin >> y;
            row[y] = 0;
        } else if (k == 4) {
            cin >> x;
            if (book[x] > 0 && !row[book[x]]) {
                cout << book[x] << '\n';
                book[x] = -1;
            } else {
                cout << "-1\n";
            }
        } else {
            cin >> x;
            if (book[x] == -1) {
                book[x] = 0;
            }
        }
    }
    return 0;
}

小美的书架# 发布于2021-04-16 上次编辑2021-04-16

问题描述#

解题思路#

小美的书架 #

发布于2021-04-16

上次编辑2021-04-16