手机串流 PS5 （ doge ）

招

@vegito2002 感觉可行，可以优化到 O(n*min(m,n))。

@contmonad 修改次数就是最长递减子序列。

DP：
原链表为 a ；
dp[n][m]，表示前 n 个数最小值大于等于 m 时需要的最小△值。
'''
def f(a):
ma = max(a)
dp = [[0] * (ma + 1) + [float("inf")] for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
for j in range(ma, -1, -1):
dp[i][j] = min(dp[i][j + 1], dp[i - 1][j] + abs(a[i - 1] - j))

return dp[len(a)][0]
'''
时间复杂度 O(n*m)

这道题基本算法就是双指针，复杂度 O(n)，但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和，则必须遍历整个数组。

@paloalto 好吧，我的错。。。

@paloalto 可是文章里用的是百分比

@DT27 这个有问题，这里“-”只能出现一次。

伪多项式时间： https://zh.wikipedia.org/wiki/%E4%BC%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%97%B6%E9%97%B4

我现在也在实习，不过正式工资已经定了。当时是直接发来的 offer ，没有谈薪资，感觉少了点，不过还好。我觉得既然是谈工资就一定往你想要的说，不行再降，否则以后肯定会后悔的。

B

@Vicer @KenGe 上个月买的，现在已经找不到了，好像涨价了，不好意思。

@KenGe 淘宝有 50 多一年的，你可以看看。

java 和 C#中好像也有，其他语言就不清楚了。

C/C++中有静态局部变量， static 关键字。静态局部变量保存在全局数据区，而不是保存在栈中，每次的值保持到下一次调用，直到下次赋新值。

@yuankui 是正解。
楼主给的数据不是时间段，是时间点，只是几个时间点连起来就是时间段了。
如果给的是若干时间段，比如原问题中
A： 3,4,5, 7,8,910, 18,19
B: 4,5, 16,17,18,19,20
写成
A：3,5,7,10,18,19
B：4,5,16,20
的话才会用到线段树。