【python刷题】Prepare Another Box

题目描述

题目链接: Prepare Another Box
玩具编号从 $1$ 到 $N$ ，玩具编号为 $N$ ，盒子编号为 $1$ 到 $N-1$ 。玩具 $i(1\le i\le N)$ 的大小为 $A_i$ ，盒子 $i(1\le i\le N-1)$ 的大小为 $B_i$ 。

高桥想把所有的玩具存放在不同的盒子里，他决定按顺序执行以下步骤：

1. 任意选择一个正整数 $x$ ，购买一个尺寸为 $x$ 的盒子。
2. 将每个 $N$ 玩具放入 $N$ 盒子中（ $N-1$ 现有盒子加上新购买的盒子）。在这里，每个玩具只能放置在一个尺寸不小于玩具尺寸的盒子里，并且盒子不能包含两个或两个以上的玩具。

他想通过在步骤 $1$ 中购买一个足够大的盒子来执行步骤 $2$ ，但是更大的盒子更贵，所以他想购买尽可能小的盒子。

判断是否存在一个值 $x$ ，使得他可以执行步骤 $2$ ，如果存在，找出最小值 $x$ 。

约束

• $2\le N\le 2\times 10^5$
• $1\le A_i,B_i\le 10^9$
• 所有输入值均为整数。

输入

格式如下
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_{N-1}$

输出

如果存在一个值 $x$ ，使得Takahashi可以执行步骤 $2$ ，那么打印最小值 $x$ 。否则，输出‘ -1 ’。

算法思路

把所有玩具排序，把所有盒子排序，从大到小把能放入当前所剩最大盒子的玩具放入，不能放入的则跳过。如果跳过了一个以上的玩具没被放入，则无解，返回-1。否则就需要一个和那个玩具一样大的盒子，即输出那个被跳过的玩具的大小。

注意复杂度！

这个题目我超时了没有通过，因为我写了如下的代码

N=int(input())
A=sorted(list(map(int, input().split())),reverse=True)
B=sorted(list(map(int, input().split())),reverse=True)
a = 0
while A:
    if B and A[0]<=B[0]: 
        A.pop(0)
        B.pop(0)
    elif a: 
        exit(print(-1))
    else:
        a = A.pop(0)
print(a)

我选择把两个数组进行降序排序
而能AC通过的代码如下

代码实现

N = int(input())
A = sorted(map(int,input().split()))
B = sorted(map(int,input().split()))
a = 0
while A:
    if B and A[-1]<=B[-1]: 
        A.pop()
        B.pop()
    elif a: 
        exit(print(-1))
    else:
        a = A.pop()
print(a)

分析

比较不难看出，AC的代码并没有采用降序，而是用升序的方法。升序处理过后，每次操作只要对最后一个元素进行查询和删除，采用的函数pop()。而如果用降序，则变成了每次操作对第一个元素进行查询和删除，则需要使用pop(0)才能实现。
为什么pop(0)的时间复杂度比pop()多这么多呢？
因为pop()是默认移除最后一个元素，只需常数时间 O(1)而pop(0)移除第一个元素后，需要移动后续所有元素，时间复杂度为O(n)

总结

对于简单题，一定要注意时间复杂度的优化，考虑内置函数使用与否，或是同一个内置函数之间，使用方式的差异。

原文地址：https://blog.csdn.net/qq_59306099/article/details/143085078

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！