小美的书架

[编程题]小美的书架

热度指数：4852 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美的书架上有很多书。小美是个爱读书的新时代好青年。

小团虽然也喜欢看书，但小团大多数时候都更喜欢来小美家蹭书读。

这就导致小美的书架上很多书都会被小团借走。

小美很烦这一点，就想出了一个招数，小美的书架是一行一行的，他会对一些行加锁，这样小团就借不走了。

现在小团想要借书，请你帮忙看看小团能不能借到书，如果可以借到的话在哪一行书架上有这本书。

为了简单起见，每本书将用一个正整数进行编号，小美的书架一共有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

示例1

输入

输出

4
-1
-1
3

备注:

对于30%的数据有 $N\leq 10, M\leq10, Q\leq 20$

对于80%的数据有 $N\leq 1000, M\leq1000, Q\leq 100000$

对于100%的数据有 $N\leq 10000, M\leq10000, Q\leq 100000$

算法知识视频讲解

Java

_叶知秋

思路：

books[]数组，用不同的值记录每本书的状态
bookshelf[]数组记录书架是否上锁
然后根据不同的情况模拟即可

注意：题目有误，应该n为书编号,m为书架编号

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 书编号
        int n = sc.nextInt();
        // 书架编号
        int m = sc.nextInt();
        // books[i]代表的状态
        // -1：借不到，行上锁/未被放到书架上/已借走
        // 0：小团借走了
        // 1-n：在编号为1-n的书架上
        int[] books = new int[n+1];
        // 初始时所有书未放到书架上，不能借
        Arrays.fill(books,-1);
        // false:未上锁    true：上锁
        boolean[] bookshelf = new boolean[m+1];
        int q = sc.nextInt();
        while(q-->0){
            int option = sc.nextInt();
            int x,y;
            switch(option){
                case 1:
                    x = sc.nextInt();
                    y = sc.nextInt();
                    // 不能放的情况，什么都不做
                    if(books[x]==0 || (books[x]>0&&bookshelf[books[x]]) || bookshelf[y]){
                        break;
                    }else{
                        books[x] = y;
                    }
                    break;
                case 2:
                    y = sc.nextInt();
                    bookshelf[y] = true;
                    break;
                case 3:
                    y = sc.nextInt();
                    bookshelf[y] = false;
                    break;
                case 4:
                    x = sc.nextInt();
                    if(books[x]>0 && !bookshelf[books[x]]){
                        System.out.println(books[x]);
                        // 被小团借走了
                        books[x] = 0;
                    }else{
                        System.out.println(-1);
                    }
                    break;
                case 5:
                    x = sc.nextInt();
                    if(books[x]==0){
                        books[x] = -1;
                    }
                    break;
                default:break;
            }
        }
    }
}

发表于 2022-03-02 15:05:04 回复(0)