蓝桥杯 商品库存管理

题目

链接

初始做法

对于每个操作，先找其余操作的并集，然后其与[1,n]的补集中元素个数就是答案

t = input().split()
n = int(t[0])
m = int(t[1])

if m == 0:
    print(n)
else:
    op = []
    for i in range(m):
        op.append(tuple(map(int, input().split())))
    if m == 1:
        print(n)
    else:
        for i in range(m):
            # 取除了第i个操作的并集
            l = n
            r = 1
            for j in range(m):
                if i == j:
                    continue
                if op[j][0] < l:
                    l = op[j][0]
                if op[j][1] > r:
                    r = op[j][1]
            else:
                print(n - r + l - 1)

结果

分析

首先我的做法确实不是最优的，但是有三个测试点错误应该是对题目的理解不同，这个网站没有考虑自始至终都没有被操作的种类，而我是考虑了的，那我们就先按照它的理解来。

然后这里涉及了对数组的多次加法操作，因此我们可以考虑用差分数组

改进做法

import sys

input=lambda:sys.stdin.readline().strip()
# 商品种类和操作次数
n,m = map(int,input().split())

# 所有的操作统计
op = []
# 差分数组
b=[0 for i in range(n+2)]
for i in range(m):
    # 该次操作的左边和右边
    l,r=map(int,input().split())
    op.append((l,r))
    # 使用差分数组对区间l~r进行累加操作，因为原始商品种类的数目都是0，因此不需要设置原始数组，差分数组就可以恢复
    b[l]+=1
    b[r+1]-=1

# 利用差分数组恢复原始数组，得到每个类别被覆盖的次数
for i in range(1,n+1):
    b[i]+=b[i-1]

# 统计一次都没被覆盖的类别数目
num_0=0
for i in range(1,n+1):
    if b[i]==0:
        num_0+=1
    # 将所有被覆盖多次的类别数量置为0，这样整个数组就可以表示所有被覆盖为1次的类别了
    elif b[i]!=1:
        b[i]=0

# 更新数组，使得b[i]表示种类0到种类i中被覆盖次数为1的种类数目
for i in range(1,n+1):
    b[i]+=b[i-1]

# 开始统计结果
for l,r in op:
    print(b[r]-b[l-1])

结果

分析

这里如果删掉input=lambda:sys.stdin.readline().strip()，会有很多测试点运行超时，结果如下：

上网搜了一下，sys.stdin.readline()从标准输入中读取一行数据，包括换行符 \n。与内置的 input() 函数相比，sys.stdin.readline() 更高效，因为它直接从输入流中读取数据，而不需要额外的处理。

但是这个加在我的第一个做法上时并没有解决我的超时问题，这说明我的第一个做法确实问题更大一点，不过这个加在第一个做法上后时间上反而还拖后了，不知道为什么