字节测开笔试10-15

第一题：好串的数目

小红有一个字符串，例如000001111011011，然后啥叫好串呢，就是前一半全0后一半全1，或者前一半全1后一半全0就是好串，问最长的好子串长度多长（连续子串是好串）。

前缀和

具体来说，有一个数组zeros用来存连续0的数目，有一个数组ones用来存连续1的数目，然后从1遍历到n，分2种情况，例如最长子串为前半0后半1的情况，就只需要找ones中有没有ones[i]可以和前面的构成好串，例如ones[i] = 2,那就去往前回退2格去看zeros[i-2]（连续1的数目）是不是能够容纳下ones[i]，如果能的话，那就可以构成至少长度为min(ones[i],zeros[i-ones[i]])*2的好子串。

代码如下：

s = input().strip()
arr = [int(x) for x in s]
n = len(arr)
zeros = [0]
ones = [0]
for x in arr:
    if x==0:
        zeros.append(zeros[-1]+1)
        ones.append(0)
    else:
        zeros.append(0)
        ones.append(ones[-1]+1)
zeros = zeros[1:]
ones = ones[1:]

res = 0
for i in range(n):
    #前一半0，后一半1
    if i-ones[i]>=0:
        res = max(res,min(ones[i],zeros[i-ones[i]])*2)
        res = max(res,min(zeros[i],ones[i-zeros[i]])*2)
print(res)

第二题：
一个坐标轴（1维）上有n个人，同时也有n个宝箱，然后位置各不同，同时还有一个终点p，任务就是这些人要去每人拿一个宝箱然后跑到终点去，每走一步消耗时间1，拿宝箱不耗时。请问最短的时间和？

输入：
n,p 代表n个人和终点p
一行整数，代表n个人坐标
一行整数，代表n个宝箱坐标
n是10^5量级

样例
input
3 3
1 4 3
2 5 6

output
11

贪心

对所有人和所有物品排序，让所有人尽可能拿离他们近的物品，然后直接跑到终点去

代码如下：

n,p = list(map(int,input().strip().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.sort()
b.sort()
res = 0
for i in range(n):
    res += abs(b[i]-a[i]) + abs(p-b[i])
print(res)