PDD 拼多多笔试 ac,ac,ac,40%
第一题
把数组a 从大到小排列，三个三个的计算。
from sys import stdin N = int(stdin.readline()) A = list(map(int, stdin.readline().split())) A.sort(reverse=True) sum_value = 0 for i in range(int(len(A) / 3)): sum_value += A[i * 3] sum_value += A[i * 3 + 1] index = int(len(A) / 3) * 3 sum_value += sum(A[index:]) print(sum_value)
第二题
开一个数组，长度为M
from sys import stdin
N, M = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
mod_dic = {0: 1}
for i in range(M):
mod_dic[i + 1] = 0
sum = 0
num = 0
for item in A:
sum += item
sum %= M
num += mod_dic[sum]
mod_dic[sum] += 1
print(num) 第三题
找到对于每个数字0-9， 使得数组中至少有k 个这样的数字，需要的代价。
排序找到代价最小的那个。
容易发现，要取得字典序最小的那个，要从后往前replace比k 小的值为k， 从前往后replace 比k 大的值为k。
from sys import stdin
import copy
def cal_cost(number, index, K, string):
if number[index] >= K:
return 0, string
else:
cost = 0
K -= number[index]
for i in range(1, 10):
if index + i < 10:
num = min(K, number[index + i])
string = string.replace(str(index + i), str(index), num)
cost += (num * i)
K -= num
if index - i >= 0:
num = min(K, number[index - i])
string = string[::-1].replace(str(index - i), str(index), num)
string = string[::-1]
cost += (num * i)
K -= num
if K == 0:
break
return cost, string
def return_first_item(item):
return item[0]
N, K = map(int, stdin.readline().split())
original_string = stdin.readline()[:-1]
number = [0 for i in range(10)]
for item in original_string:
number[ord(item) - ord('0')] += 1
list = []
for i in range(10):
cost, best_choice = cal_cost(number, i, K, copy.copy(original_string))
list.append((cost, best_choice))
list.sort(key=return_first_item)
min_value, string = list[0]
for item in list:
if item[0] > min_value:
break
string = min(string, item[1])
print(min_value)
print(string) 第四题 dp, 我的算法复杂度为O(N^2)
只过了40%
from sys import stdin N, K = map(int, stdin.readline().split()) C = list(map(int, stdin.readline().split())) dp = [[0 for i in range(N + 1)] for j in range(K + 1)] dp[0][0] = 0 dp[0][1] = 1 for i in range(1, N + 1): if C[i - 1] == C[i - 2]: dp[0][i] = dp[0][i - 1] + 1 if dp[0][i] >= N - K: print(N - K) exit() else: dp[0][i] = 1 for i in range(1, K + 1): dp[i][0] = 0 dp[i][1] = 1 for j in range(2, N + 1): dp[i][j] = 1 for k in range(min(i + 1, j)): if C[j - 1] == C[j - k - 2]: dp[i][j] = max(dp[i][j], dp[i - k][j - k - 1] + 1) print(max(dp[K]))
