京东笔试，算法两题
n, m = map(int, input().split()) nums = list(map(int, input().split())) nums.sort() #贪心 sums = [0]*(len(nums)+1) for i in range(len(nums)):sums[i+1] = sums[i] + nums[i] dp = [0] * (n+1) #DP, dp[i]表示卖i支股票的最小亏损, O(N)复杂度 for i in range(1, n+1): if i <= m: dp[i] = sums[i] else: dp[i] = dp[i-m] + sums[i] for i in range(int(input())): print(dp[int(input())])
AC 27%
def gcd(a, b):
c = a % b
if c == 0:
return b
else:
return gcd(b, c)
def calc_k(point1, point2):
y_diff = point2[1] - point1[1]
x_diff = point2[0] - point1[0]
if x_diff == 0:
return (float('inf'), float('inf'))
elif y_diff == 0:
return (0, 0)
else:
if x_diff * y_diff > 0:
x_diff, y_diff = abs(x_diff), abs(y_diff)
else:
x_diff, y_diff = -(abs(x_diff)), abs(y_diff)
gcd_factor = gcd(x_diff, y_diff)
return (x_diff//gcd_factor, y_diff//gcd_factor)
points = []
from collections import defaultdict
ks = defaultdict(list)
for i in range(int(input())):
points.append(list(map(int, input().split())))
for i in range(len(points)-1):
for j in range(i+1, len(points)):
ks[calc_k(points[i], points[j])].append((i, j))
ks = sorted(ks.items(), key=lambda e:len(e[1]), reverse=True)
ans = 0
vis = set()
for k, vs in ks:
if len(vs) == 1:break
ans += len(vs) * (len(vs)-1) // 2
for v in vs:
vis.add(v[0])
vis.add(v[1])
if len(vis) == len(points):break #测试集太弱了，这都能AC
print(ans) 