PAT-2021年秋季考试 乙级 7-4 数组与链表 (20 分)

题目

让我们来设计这样一种数组与链表结合的整数存储的结构 A：

这种结构首先初始化一个长度为 L

0

的整型数组 A

0

，返回给用户使用。当用户访问第 i 个元素 Ai 的时候，如果 0≤i<L

0

，则 Ai 对应 A

0

i，系统就返回 h

0

+i×sizeof(int) 作为要访问的地址，其中 h

0

是数组 A

0

的起始位置，sizeof(int) 是数组元素的大小，这里元素就是 int 型，占 4 个字节。

当用户访问越界时（即 i≥L

0

），系统将另外开辟一个长度为 L

1

的数组 A

1

。此时 Ai 对应 A

1

j（这里 i 和 j 之间的映射关系留给你去推导）。如果 0≤j<L

1

，则返回 h

1

+j×sizeof(int) 作为要访问的地址，其中 h

1

是数组 A

1

的起始位置。

当 A

1

j 继续越界时，系统就按照上述规则继续开辟另一个长度为 L

2

的数组 A

2

，并以此类推。

本题就请你实现这个系统功能，为用户的任何一次访问返回对应元素的地址。

输入格式：

输入第一行给出两个正整数 N（≤10

4

）和 K（≤10

3

），分别为最多允许开出的数组个数、以及用户访问的次数。

此后 N 行，每行给出两个正整数，分别是一个数组的初始地址（≤10

7

）和长度（≤100），其间以空格分隔。题目保证这些数组占据的空间无重叠。

最后一行顺序给出 K 个用户访问的数组下标，为区间 [0,2

20

] 内的整数。

输出格式：

对每个用户访问，在一行中输出对应的地址。但如果用户的访问超出了 N 个数组的存储范围，则这个访问是非法的，要输出 Illegal Access，并且对这个访问不采取任何处理。

最后一行请输出上述过程中一共创建了多少个数组。

输入样例：
6 7
2048 5
128 6
4016 10
1024 7
3072 12
9332 10
2 12 25 50 28 8 39
输出样例：
2056
4020
1040
Illegal Access
3072
140
3116
5

样例说明：

访问 A2 即 A

0

2，元素的地址就是 2048+2×4=2056。

访问 A12，则只加开 A

1

不够，需要加开 A

2

，其初始位置 h

2

=4016，则 A12=A

2

1 的地址就是 4016+1×4=4020。

访问 A25，则必须加开 A

3

，其初始位置 h

3

=1024，则 A25=A

3

4 的地址就是 1024+4×4=1040。

访问 A50 超出了允许创建的数组的最大边界，所以是非法访问，新数组未创建。

访问 A28，则必须加开 A

4

，其初始位置 h

4

=3072，则 A28=A

4

0 的地址就是 3072。

访问 A8=A

1

3，所以地址是 128+3×4=140。

访问 A39=A

4

11，地址就是 3072+11×4=3116。

上述访问一共创建了 5 个数组。

解题思路

N, K = map(int,input().split())
# N, K = map(int,"6 7".split())
testList = []
maxLength = 0
neicunDict = dict()
for i in range(N):
    x,y = map(int,input().split())
    # x, y = map(int, "2048 5".split())
    maxLength += y
    testList.append(y)
    neicunDict[i] = x

inputList = list(map(int, input().split()))
# inputList = list(map(int, "2 12 25 50 28 8 39".split()))

maxShuzu = 0
for i in inputList:
    if i >= maxLength:
        print("Illegal Access")
        continue
    for index,y  in enumerate(testList):
        if (i - y)<0:
            neicundizhi = neicunDict[index]
            address = neicundizhi+i*4
            print(address)
            maxShuzu = max(index+1,maxShuzu)
            break
        i -= y
print(maxShuzu)