✕
![preview]()
新鲜事
原文
论CSP-S T1的一个雷霆做法
今年s组的T1我有一个很神奇的做法，就是排序后求a[i+1]-a[i]存到一个数组b里然后求b的前缀和c数组，再求c的前缀和d数组，发现将m块宝石搞成一样的（最大一块为a[i]）需要花费的代价是（（（m-1）*c[i]）-d[i-1]）+d[i-m+1]，应该是这个式子（我忘了），然后就是用e数组存放要填到a[i]最多能填平几个石头，然后把上面式子的块数换成e[i-1]，超过次数就减一块，直到够用之后把现在的块数存进e[i]，这样除去sort最多是O(n)的复杂度。 说实话我能写出这个做法也是神了，我都不知道我是怎么想出来的，大概是请神上身了吧（）好像洛谷题解区有一个做法和我这个相同？我也不知道嘿嘿（）代码就不放了因为我忘了
