第一题:好串的数目小红有一个字符串,例如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 = 0for 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量级样例input3 31 4 32 5 6output11贪心对所有人和所有物品排序,让所有人尽可能拿离他们近的物品,然后直接跑到终点去代码如下: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 = 0for i in range(n):    res += abs(b[i]-a[i]) + abs(p-b[i])print(res)
点赞 3
评论 3
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务