美团8.19笔试

小美的数组操作

小美拿到了一个数组，她每次可以进行如下操作：选择两个元素，一个加 1，另一个减 1。

小美希望若干次操作后，众数的出现次数尽可能多。你能帮她求出最小的操作次数吗？

众数定义：在一组数据中，出现次数最多的数据，是一组数据中的原数据，而不是相应的次数。一组数据中的众数不止一个，如数据2、3、-1、2、1、3中，2、3都出现了两次，它们都是这组数据中的众数。

输入描述：

第一行为一个正整数，代表数组的大小。第二行输入个正整数，代表小美拿到的数组。

输出描述：一个整数，代表最小的操作次数。

答案：

nums = list(map(int, input().split()))
sumization = sum(nums)
res = 0
if not sumization % n:
    mean = sumization // n
    res += sum(num - mean for num in nums if num > mean)
else:
  #去掉最小最大，平均数加一位或者减一位
    nums = sorted(nums)
    mean = (sumization - nums[-1]) // (n - 1)
    res = sum(num - mean for num in nums[:-1] if num > mean)
    mean = (sumization - nums[-1]) // (n - 1) + 1
    res = min(res, sum(mean - num for num in nums[:-1] if num < mean))
    mean = (sumization - nums[0]) // (n - 1)
    res = min(res, sum(num - mean for num in nums[1:] if num > mean))
    mean = (sumization - nums[0]) // (n - 1) + 1
    res = min(res, sum(mean - num for num in nums[1:] if num < mean))
print(res)

小美的数组构造

小美拿到了一个数组a，她准备构造一个数组n

满足：

1.b的每一位都和a对应位置不同

2.b的所有元素之和都和a相同。

3.b的数组均为正整数。

请你告诉小美有多少种构造方式。由于答案过大，请对10**9+7取模。

n = int(input())
nums = list(map(int,input().split()))
sumization = sum(nums)
C = 10**9 + 7
dp = [[0] * (sumization+1) for _ in range(n)]
dp[0] = [1] * (sumization+1)
dp[0][nums[0]] = 0
dp[0][0] = 0
for i in range(1,n):
    for j in range(i+1,sumization+1):
        for k in range(1,j-i+1):
            # print(i,j,k)
            if k == nums[i]:
                continue
            dp[i][j] += dp[i-1][j-k]
            dp[i][j] %= C

小美的01串翻转

小美定义一个 01 串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。

例如，"10001"的权值是 1，因为只需要修改一次：对第三个字符取反即可。

现在小美拿到了一个 01 串，她希望你求出所有非空连续子串的权值之和，你能帮帮她吗？

输入描述：一个仅包含'0'和'1'的字符串，长度不超过 2000。

输出描述：所有非空子串的权值和。

示例1

输入例子：10001

输出例子：8

例子说明：长度为 2 的子串中，有 2 个"00"的权值是 1。长度为 3 的 3 个子串权值都是 1。长度为 4 的 2 个子串权值都是 1。长度为 5 的 1 个子串权值是 1。总权值之和为 2+3+2+1=8

s = [int(c) for c in input()]
n = len(s)
s1,s2 = s[:],s[:]
s2[0]^=1
for i in range(1,n):
    s1[i]=s1[i-1]^1
    s2[i]=s2[i-1]^1
dp = [[0]*(n+1),[0]*(n+1)]

for i in range(1,n+1):
    if s[i-1] !=s1[i-1]:
        dp[0][i] = dp[0][i-1]+1
        dp[1][i] = dp[1][i-1]
    else:
        dp[0][i] = dp[0][i-1]
        dp[1][i] = dp[1][i-1]+1
res = 0        
for i in range(n):
    for j in range(i+1,n):
        res += min(dp[0][j+1]-dp[0][i],dp[1][j+1]-dp[1][i])
print(res)