请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 样例输出 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
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-3.5, 由博主 GISer Liu 编写：

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

问题分析

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

解决思路

1. 输入处理：读取输入数据，包括数据组数 ( T )，每组数据的山数 ( n )，初始高度 ( h_i ) 和高度差 ( a_i )。
2. 计算最小花费：
   • 对于每组数据，我们需要计算从第二座山开始，每座山需要调整的高度。
   • 具体来说，对于第 ( i ) 座山，其目标高度应为 ( h_{i-1} + a_i )。
   • 如果 ( h_i ) 小于目标高度，则需要增加 ( h_i ) 到目标高度，计算花费。
   • 如果 ( h_i ) 大于目标高度，则需要减少 ( h_i ) 到目标高度，但要注意 ( h_i ) 不能小于 1。
3. 输出结果：输出每组数据的最小花费。

代码实现

以下是详细的 C++ 代码实现：

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

using namespace std;

int main() {
    int id;
    cin >> id; // 数据组 id
    int T;
    cin >> T; // 数据组数

    while (T--) {
        int n;
        cin >> n; // 山的数量
        vector<int> h(n); // 初始高度
        vector<int> a(n - 1); // 高度差

        for (int i = 0; i < n; ++i) {
            cin >> h[i];
        }

        for (int i = 0; i < n - 1; ++i) {
            cin >> a[i];
        }

        long long cost = 0; // 最小花费

        for (int i = 1; i < n; ++i) {
            int target_height = h[i - 1] + a[i - 1];
            if (h[i] < target_height) {
                cost += target_height - h[i];
                h[i] = target_height;
            } else if (h[i] > target_height) {
                if (target_height < 1) {
                    cost += h[i] - 1;
                    h[i] = 1;
                } else {
                    cost += h[i] - target_height;
                    h[i] = target_height;
                }
            }
        }

        cout << cost << endl;
    }

    return 0;
}

代码解释

1. 输入处理：

   • 读取数据组 id 和数据组数 ( T )。
   • 对于每组数据，读取山的数量 ( n )，初始高度 ( h_i ) 和高度差 ( a_i )。

2. 计算最小花费：

   • 使用一个循环遍历每座山，从第二座山开始。
   • 计算每座山的目标高度 ( h_{i-1} + a_i )。
   • 如果当前高度 ( h_i ) 小于目标高度，则增加 ( h_i ) 到目标高度，并计算花费。
   • 如果当前高度 ( h_i ) 大于目标高度，则减少 ( h_i ) 到目标高度，但要注意 ( h_i ) 不能小于 1。

3. 输出结果：

   • 输出每组数据的最小花费。

总结

通过上述分析和代码实现，我们可以有效地解决 XZH 的审美问题，并计算出最小花费。希望这个解决方案能满足您的需求。如果有任何问题或需要进一步的解释，请随时告知。

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