前言

alt

题解

最近空闲的时间多了一些，补一下之前的题解

E. 小红的矩阵划分

思路：三分

这个n为偶数，其实很值得玩味

我的猜测结论是

这样的话

最终为

这是一个奇怪的函数，要么其满足单调性，要么满足凸函数性质（赌）

那就引入三分的解法(单调性是特殊的凸函数)

n, x, y = list(map(int, input().split()))

# 评估函数
def evaulate(m):
    left = n * n - m * 4
    return left // 3 * x + m * y

# 三分板子
l, r = 0, (n//2) ** 2
while r - l >= 3:
    d = (r - l) // 3
    m1 = l + d
    m2 = r - d
    c1 = evaulate(m1)
    c2 = evaulate(m2)
    if c1 <= c2:
        l = m1
    else:
        r = m2
        
res = 0
# 扩大范围
for i in range(max(0, l - 10), min(l + 10, (n // 2) ** 2) + 1):
    res = max(res, evaulate(i))
    
print (res)

写在最后

alt