题解 | 做项目的最大收益问题

package main

import (
	"container/heap"
	"fmt"
)

type Elem struct {
	Cost  int
	Profi int
}
type MinHeap struct {
	Data []Elem
}

func ConstructMinHeap(e []Elem) *MinHeap {
	return &MinHeap{
		Data: e,
	}
}
func (m MinHeap) Len() int {
	return len(m.Data)
}
func (m MinHeap) Less(i, j int) bool {
	return m.Data[i].Cost < m.Data[j].Cost
}
func (m MinHeap) Swap(i, j int) {
	m.Data[i], m.Data[j] = m.Data[j], m.Data[i]
}
// 弹出在go中写最后，模拟down过程
func (m *MinHeap) Pop() interface{} {
	x := m.Data[len(m.Data)-1]
	m.Data = m.Data[:len(m.Data)-1]
	return x
}
func (m *MinHeap) Push(x interface{}) {
	m.Data = append(m.Data, x.(Elem))
}

func (m *MinHeap) Front() Elem {
	return m.Data[0]
}

type MaxHeap struct {
	Data []Elem
}

func ConstructMaxHeap() *MaxHeap {
	return &MaxHeap{
		Data: make([]Elem, 0),
	}
}
func (m MaxHeap) Len() int {
	return len(m.Data)
}
func (m MaxHeap) Less(i, j int) bool {
	return m.Data[i].Profi > m.Data[j].Profi
}
func (m MaxHeap) Swap(i, j int) {
	m.Data[i], m.Data[j] = m.Data[j], m.Data[i]
}
func (m *MaxHeap) Pop() interface{} {
	x := m.Data[len(m.Data)-1]
	m.Data = m.Data[:len(m.Data)-1]
	return x
}
func (m *MaxHeap) Push(x interface{}) {
	m.Data = append(m.Data, x.(Elem))
}

func main() {
	N, W, K := 0, 0, 0
	for {
		n, _ := fmt.Scan(&N, &W, &K)
		if n == 0 {
			break
		} else {
			cost, profi := make([]int, N), make([]int, N)
			for i := 0; i < N; i++ {
				fmt.Scan(&cost[i])
			}
			for i := 0; i < N; i++ {
				fmt.Scan(&profi[i])
			}
			ele := make([]Elem, N)
			for i := 0; i < N; i++ {
				ele[i] = Elem{Cost: cost[i], Profi: profi[i]}
			}
			// 基于cost构建小根堆
			minheap := ConstructMinHeap(ele)
			heap.Init(minheap)
			// 基于profi构建大根堆
			maxHeap := ConstructMaxHeap()
			heap.Init(maxHeap)

			for K > 0 {
			    // 花费只要小于已有成本，加入到大根堆
				for minheap.Len() > 0 && minheap.Data[0].Cost <= W {
					e := heap.Pop(minheap).(Elem)
					heap.Push(maxHeap, e)
				}
				if maxHeap.Len() == 0 {
					break
				}
			    // 每次从大根堆中弹出利润最大的，累加利润
				e := heap.Pop(maxHeap).(Elem)
				W += e.Profi
				K--
			}
			fmt.Println(W)
		}
	}
}