请C++回答 山 问题 数学问题

Question

4.山
题目描述
XZH 非常喜欢山。
身为美术学校毕业的 XZH 对山的形状有一定的要求。他希望对于 i∈[2,n]，第 i 座山比第 i−1 座山恰好高 ai 的高度。
每座山有初始高度，第 i 座山的初始高度为 hi 。
同时，他可以使用“膜法”来让一座山的高度 hi 变为他想要的任意高度，但这一操作会消耗 XZH 1 元。
考虑到山必定是一个有高度的实体，不能直接把它夷为平地或者变成一个坑，所以他的功能有一定的限制，改变之后，山的高度需要满足 hi ≥1。
求 XZH 花费的最小值，让山达到他的审美。
输入格式第一行输出一个整数 id，表示数据组，帮助大家取得部分分。(其中，样例的 id 设为 0)。
第二行输入一个整数 T。
对于每一组数据：第一行输入一个整数 n。
第二行输入 n 个整数，第 i 个整数表示第 i 座山的高度 hi 。
第三行输入 n−1 个数，第 i 个数表示 XZH 希望第 i 座山比第 i+1 座山矮 ai 。
输出格式一行，一个整数，表示 XZH 的最小花费。
样例
样例输入 1
0
2
5
1 2 5 3 2
1 1 0 -1
7
1 9 1 9 8 1 1
1 1 4 5 1 4
样例输出 1
1
6
样例说明
样例 1 解释：对于第一组样例，一种可行的实现是，把 h3 改成 3 即可。
对于第二组样例，一组可行的实现是，将数列 h 改为 {1,2,3,7,12,13,17}，可能有多组解，但是可以证明没有任意一组解比样例给出的值更小。
提示
id 特殊性质 数据占比
1 n=2 10%
2 1≤n≤1000 30%
3 hi =1,ai ≥0 15%
4 ai =0 15%
5 无 30%
对于 100% 的数据 1≤n≤105,−10≤ai ≤10,1≤hi ≤106,1≤T≤6。

给个C++源码吧

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

好的，我们来详细分析并解决这个问题。

问题分析

XZH 希望对于 ( i \in [2, n] )，第 ( i ) 座山比第 ( i-1 ) 座山恰好高 ( a_i ) 的高度。每座山有初始高度 ( h_i )。XZH 可以使用“膜法”来让一座山的高度 ( h_i ) 变为他想要的任意高度，但这一操作会消耗 XZH 1 元。改变之后，山的高度需要满足 ( h_i \geq 1 )。我们需要求 XZH 花费的最小值，让山达到他的审美。

解决思路

1. 初始化：读取输入数据，包括山的数量 ( n )、每座山的初始高度 ( h_i ) 以及每座山之间的相对高度 ( a_i )。
2. 计算目标高度：根据 ( a_i ) 计算每座山的目标高度。
3. 计算最小花费：遍历每座山，计算将当前山的高度调整到目标高度所需的最小花费。

具体解决方案

1. 读取输入：读取数据组数 ( T )，对于每组数据，读取山的数量 ( n )、每座山的初始高度 ( h_i ) 以及每座山之间的相对高度 ( a_i )。
2. 计算目标高度：根据 ( a_i ) 计算每座山的目标高度。
3. 计算最小花费：遍历每座山，计算将当前山的高度调整到目标高度所需的最小花费。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int id;
    cin >> id;
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> h(n);
        for (int i = 0; i < n; ++i) {
            cin >> h[i];
        }
        vector<int> a(n - 1);
        for (int i = 0; i < n - 1; ++i) {
            cin >> a[i];
        }

        // 计算目标高度
        vector<int> target(n);
        target[0] = h[0];
        for (int i = 1; i < n; ++i) {
            target[i] = target[i - 1] + a[i - 1];
        }

        // 计算最小花费
        long long cost = 0;
        for (int i = 0; i < n; ++i) {
            if (target[i] < 1) {
                cost += 1 - target[i];
                target[i] = 1;
            } else if (h[i] < target[i]) {
                cost += target[i] - h[i];
            }
        }

        cout << cost << endl;
    }
    return 0;
}

代码解释

1. 输入读取：
   • 读取数据组数 ( T ) 和每组数据的山数量 ( n )、每座山的初始高度 ( h_i ) 以及每座山之间的相对高度 ( a_i )。
2. 计算目标高度：
   • 根据 ( a_i ) 计算每座山的目标高度 ( target )。
3. 计算最小花费：
   • 遍历每座山，计算将当前山的高度调整到目标高度所需的最小花费。如果目标高度小于1，则将其调整为1并计算花费。

总结

通过上述分析和代码实现，我们可以有效地解决这个问题，计算出 XZH 花费的最小值，让山达到他的审美。希望这个解决方案对您有所帮助！

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑