今天做一道模板题，感觉题目答案都告诉你了

https://www.acwing.com/problem/content/150/

每次合并最小的两堆就可以
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    
    // 使用优先队列（最小堆）来存储果子堆
    priority_queue<int, vector<int>, greater<int>> pq;
    
    // 读取每种果子的数目并加入优先队列
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        pq.push(num);
    }
    
    int total_cost = 0;
    
    // 每次合并最小的两堆，直到只剩下一个堆
    while (pq.size() > 1) {
        // 取出最小的两堆
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
        
        // 合并这两堆，并将合并后的堆加入优先队列
        int new_pile = first + second;
        pq.push(new_pile);
        
        // 累加合并的体力消耗
        total_cost += new_pile;
    }
    
    // 输出最小的体力耗费值
    cout << total_cost << endl;
    
    return 0;
}
```


Go版本

```go
package main

import (
	"container/heap"
	"fmt"
)

// 定义一个最小堆的接口
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	var n int
	fmt.Scan(&n)

	// 初始化最小堆
	h := &MinHeap{}
	heap.Init(h)

	// 读取每种果子的数目并加入最小堆
	for i := 0; i < n; i++ {
		var num int
		fmt.Scan(&num)
		heap.Push(h, num)
	}

	totalCost := 0

	// 每次合并最小的两堆，直到只剩下一个堆
	for h.Len() > 1 {
		// 取出最小的两堆
		first := heap.Pop(h).(int)
		second := heap.Pop(h).(int)

		// 合并这两堆，并将合并后的堆加入最小堆
		newPile := first + second
		heap.Push(h, newPile)

		// 累加合并的体力消耗
		totalCost += newPile
	}

	// 输出最小的体力耗费值
	fmt.Println(totalCost)
}
```

最后是ruby


```ruby
class MinHeap
  def initialize
    @heap = []
  end

  def push(value)
    @heap << value
    heapify_up(@heap.size - 1)
  end

  def pop
    return nil if @heap.empty?

    swap(0, @heap.size - 1)
    min_value = @heap.pop
    heapify_down(0)
    min_value
  end

  private

  def parent(index)
    (index - 1) / 2
  end

  def left_child(index)
    2 * index + 1
  end

  def right_child(index)
    2 * index + 2
  end

  def swap(i, j)
    @heap[i], @heap[j] = @heap[j], @heap[i]
  end

  def heapify_up(index)
    while index > 0 && @heap[parent(index)] > @heap[index]
      swap(index, parent(index))
      index = parent(index)
    end
  end

  def heapify_down(index)
    loop do
      left = left_child(index)
      right = right_child(index)
      smallest = index

      smallest = left if left < @heap.size && @heap[left] < @heap[index]
      smallest = right if right < @heap.size && @heap[right] < @heap[smallest]

      break if smallest == index

      swap(index, smallest)
      index = smallest
    end
  end
end

def min_cost_to_merge_fruits(n, fruits)
  heap = MinHeap.new
  fruits.each { |fruit| heap.push(fruit) }

  total_cost = 0

  while heap.size > 1
    first = heap.pop
    second = heap.pop
    new_pile = first + second
    total_cost += new_pile
    heap.push(new_pile)
  end

  total_cost
end

# 读取输入
n = gets.to_i
fruits = gets.split.map(&:to_i)

# 计算并输出最小的体力耗费值
puts min_cost_to_merge_fruits(n, fruits)
```

9.17算法题，贪心

最近在學習ruby，因爲認識了很多日本朋友，他們那邊可能是用ruby比較多，都問我會不會ruby，早上起來就安裝了一下，很簡單，記錄下步驟

首先要安裝ruby集成環境

https://s3.jcloud.sjtu.edu.cn/899a892efef34b1b944a19981040f55b-oss01/github-release/oneclick/rubyinstaller2/releases/download/RubyInstaller-3.3.3-1/rubyinstaller-devkit-3.3.3-1-x64.exe

在這裏下載就好，下載好了一直安裝回車，就好

接下來是用gem，這是ruby的包管理工具，一般像如下使用
```sh
gem install xxx # 包名

```
很簡單

然後是換源，這個在國内真的是逃不掉

```
gem sources # ミラーソースを確認

gem sources --remove https://rubygems.org # デフォルトのソースを削除

gem sources -a https://gems.ruby-china.com # 新しいソースを追加

gem sources --add https://mirrors.tuna.tsinghua.edu.cn/rubygems/ # 別のソースを追加

gem sources -u # ソースを更新
```

這樣就可以了，接下來安裝ruby流行的web後端框架，rails
```
gem install rails
```

這個好像很流行很强大

然後還發現個寶藏框架

sinatra

真的很簡潔，第一次見比flask,fastapi還簡介的框架

```ruby
require 'sinatra'

# 定义一个根路径的 GET 请求处理程序
get '/' do
  "Hello, World!"
end

# 定义一个带有参数的路径
get '/hello/:name' do
  "Hello, #{params[:name]}!"
end

# 定义一个 POST 请求处理程序
post '/submit' do
  "You submitted: #{params[:message]}"
end
```

![image.png](/static/img/d421e891c2f276954aa0aeb5cecdf8f3.image.webp)

ruby學習

今天做https://www.acwing.com/problem/content/description/103/

直接模拟就可以，首先全部初始化高度为最高，对于每对关系，把中间的牛高度-1，可能有重复关系所以要去重


```cpp
#include <iostream>
#include <algorithm>
using namespace std;
void max_heights(int n, int p, int h, int m, int relations[][2]) {
    // 初始化每头牛的身高为 H
    int heights[n];
    fill(heights, heights + n, h);
    // 记录已经处理过的区间
    bool processed_intervals[n][n];
    fill(&processed_intervals[0][0], &processed_intervals[0][0] + n * n, false);
    for (int i = 0; i < m; ++i) {
        int a = relations[i][0];
        int b = relations[i][1];
        // 确保 a < b
        if (a > b) swap(a, b);
        // 如果这个区间还没有被处理过
        if (!processed_intervals[a - 1][b - 1]) {
            // 在 a 和 b 之间的牛的身高减去 1
            for (int j = a; j < b - 1; ++j) {
                heights[j] -= 1;
            }
            // 记录这个区间已经被处理过
            processed_intervals[a - 1][b - 1] = true;
        }
    }
    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << heights[i] << endl;
    }
}
int main() {
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    int relations[m][2];
    for (int i = 0; i < m; ++i) {
        cin >> relations[i][0] >> relations[i][1];
    }
    // 计算每头牛的最大可能身高
    max_heights(n, p, h, m, relations);
    return 0;
}

```

最高的牛，模拟题

https://www.acwing.com/problem/content/131/

今天这题，dfs爆搜



- dfs爆搜，注意20剪枝
- 所有火车都进栈出栈这代表一个结果产生
- 车站不为空就能选择出栈
- 如果还有火车未进栈，则可以选择进栈

```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n;  // 火车数量
vector<string> result;  // 存储所有可能的出栈顺序
stack<int> station;  // 模拟车站栈
vector<int> current;  // 当前出栈的火车顺序

// 深度优先搜索函数
void dfs(int inStack) {
    // 如果已经找到20种方案，停止搜索
    if (result.size() >= 20) {
        return;
    }

    // 如果所有火车都已进栈且栈为空，表示所有火车都已出栈
    if (inStack == n && station.empty()) {
        string s;
        // 将当前出栈顺序转换为字符串
        for (int v : current) {
            s += to_string(v);
        }
        // 将结果加入结果集
        result.push_back(s);
        return;
    }

    // 如果栈不为空，进行出栈操作
    if (!station.empty()) {
        int top = station.top();  // 获取栈顶元素
        station.pop();  // 出栈
        current.push_back(top);  // 将出栈的火车加入当前出栈顺序
        dfs(inStack);  // 递归调用dfs
        current.pop_back();  // 回溯，移除最后一个出栈的火车
        station.push(top);  // 将出栈的火车重新入栈
    }

    // 如果还有火车未进栈，进行进栈操作
    if (inStack < n) {
        station.push(inStack + 1);  // 将下一列火车进栈
        dfs(inStack + 1);  // 递归调用dfs
        station.pop();  // 回溯，移除最后一个进栈的火车
    }
}

int main() {
    cin >> n;  // 读取火车数量
    dfs(0);  // 调用dfs函数开始搜索

    // 输出前20种方案
    for (int i = 0; i < result.size() && i < 20; i++) {
        cout << result[i] << endl;
    }

    return 0;
}

```
然后最近在学习ruby

```ruby
require 'set'

# 全局变量
$n = 0
$result = []
$station = []
$current = []

# 深度优先搜索
def dfs(in_stack)
  return if $result.size >= 20

  if in_stack == $n && $station.empty?
    # 所有火车都已出栈
    $result << $current.join
    return
  end

  if !$station.empty?
    # 出栈操作
    top = $station.pop
    $current << top
    dfs(in_stack)
    $current.pop
    $station.push(top)
  end

  if in_stack < $n
    # 进栈操作
    $station.push(in_stack + 1)
    dfs(in_stack + 1)
    $station.pop
  end
end

# 主函数
def main
  $n = gets.to_i
  dfs(0)

  # 按字典序排序
  $result.sort!

  # 输出前20种方案
  $result[0, 20].each { |r| puts r }
end

# 运行主函数
main
```