The solution:
This is a counting sort problem.
we can define two lists:
L = [0]*2001 F = [0]*4001
L is a list, its index is each wood's length, its element value is the number of this length. The max index 2000 is one wood's max length.
F is a list, its index is two wood's length that is one block fence, its element value is the number of this fence length. The max index 4000 is two woods max length.
Assume input a wood its length is p, then L[p] += 1, because length p has one wood.
For loop i from 0 to the end of L , i is the length of each wood
for loop j from i to the end of L, j is the length of each wood too
if i == j, F[i+j] = L[i]//2, i+j is one fence's length
if i != jh, F[i+j] = min(L[i], L[j]), i+j is one fence's length
For loop F, find max length and block number
print max length and block number
N = int(input())
boards = input().split(" ")
L = [0]*2001
F = [0]*4001
for board in boards:
L[int(board)] += 1
for i in range(0, len(L) - 1):
for j in range(i, len(L)):
if i == j:
F[i + j] += L[i] // 2
else:
F[i + j] += min(L[i], L[j])
longest, size = 0, 0
for fenceLength in F:
if fenceLength > longest:
longest = fenceLength
size = 1
elif fenceLength == longest:
size += 1
print(longest, size)
Comments