算简单的hard, 满快就有想法了
不过写起来有点卡
2163. Minimum Difference in Sums After Removal of Elements
思路 :
这题firstsum要尽量小、secondsum要尽量大
先把前n个elements加起来得到firstsum并且放到MaxHeap里面
再来将后2*n个元素依照大小排序, 排序后的最大的n个elements总和为secondsum
并且记录排序前后的index的对照表
接着就是从nums[n]开始
如果nums[i]比MaxHeap中最大的值还小, 就nums[i]替换到firstnum
再来如果nums[i]是在secondsum里
那就把secondsum-nums[i]并加入剩余elements中最大的值
这样就能得到答案了
golang code :
type maxheap []int
func (this maxheap) Len() int { return len(this) }
func (this maxheap) Less(i, j int) bool { return this[i] > this[j] }
func (this maxheap) Swap(i, j int) { this[i], this[j] = this[j], this[i]
}
func (this *maxheap) Push(x interface{}) { *this = append(*this, x.(int)) }
func (this *maxheap) Pop() interface{} {
n := len(*this)
res := (*this)[n-1]
(*this) = (*this)[:n-1]
return res
}
func minimumDifference(nums []int) int64 {
firstSum, secondSum := 0, 0
n := len(nums) / 3
last2nSortByVal := make([][2]int, 2*n)
arr := make([]int, 2*n)
for i := 0; i < 2*n; i++ {
last2nSortByVal[i][0] = i
last2nSortByVal[i][1] = nums[i+n]
}
slices.SortFunc(last2nSortByVal, func(i, j [2]int) int { return i[1] - j[1] }
)
for i := 0; i < 2*n; i++ {
arr[last2nSortByVal[i][0]] = i
}
leftPartHeap := maxheap{}
for i := 0; i < n; i++ {
firstSum += nums[i]
secondSum += last2nSortByVal[2*n-1-i][1]
heap.Push(&leftPartHeap, nums[i])
}
start := n
ans := firstSum - secondSum
rec := make([]bool, 2*n)
for i := 0; i < n; i++ {
numIdx := i + n
if leftPartHeap[0] > nums[numIdx] {
tmp := heap.Pop(&leftPartHeap).(int)
heap.Push(&leftPartHeap, nums[numIdx])
firstSum = firstSum - tmp + nums[numIdx]
}
if arr[i] >= start {
secondSum -= nums[numIdx]
start