本帖仅用于探讨通用 AI 解算法题的能力。

本人发表的内容采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

敝校 2015 年 ACM 新生赛中，有两个题目是我出的。当时敝校没有自己的 OJ ，用的杭电 HDOJ 开了网络比赛并设了密码，我相信如果 HDOJ 没出问题的话，爬虫是肯定爬不到这个题面的。当然该题的思路和标准解法被发在我曾经的博客中，或许经过推理之后能够发现该内容，但既然你都推出来了，想必也用不上我的答案了对吧。

题解： https://www.cnblogs.com/BlackStorm/p/4988115.html
其他人尝试问 AI 的结果：
我第一次尝试问 AI 的结果：

以下分享得出正解的全过程，包括未公开的题面。我先简单概括一下：

我先介绍了题面的构成， AI 表示理解；
我贴出完整的题面， AI 生成了一个错误答案；
我并不想多废话，直接让 AI 重新生成，得到一个差不多正确的答案；
我提示该解法在极端情况下会发生 int 整型溢出， AI 重新给出修正后的答案；

提问 1 - 介绍题面组成

I have a problem written in Chinese, you must understand it and work out a proper solution in C++. Note that the problem consisted of 5 sections, meaning of every parts are explained as following:

Problem Description: as it being stated, the description of the problem itself.
Input: stating the constraint of the data set that will be passed to your solution.
Output: stating the requirements that the results from your solution must satisfy.
Sample Input: you're not conscious of all the data set, so it's just a sample show you what kind of data will be passed to your solution.
Sample Output: that's the expected output your solution should work out for the Sample Input.

Do you understand?

回答 1 - 确认回复

Yes, I understand. Please provide me with the problem description and I will try my best to provide you with a solution in C++.

提问 2 - 给出完整题面

Here's the problem:

Problem Description

Zyj 发明了一台 3D 打印机，但他的技术不过关，这台打印机的喷嘴频繁喷喷停停的话是会坏掉哒，所以 Zyj 为了尽量保证喷嘴能够尽量连续地喷出物料，设计了一个很蠢的方法：
一个打印物件可以大致分为 n 个部分，每个部分要求达到高度 h_i 。每次可以选择从第 L 部分到第 R 部分(L <= R)喷上一层物料，可以增加高度 1 。请你帮助他算一算，对于给定的打印物件，至少需要喷涂多少次物料。

Input

第一行是整数 T ，代表测试数据的组数(T <= 10)。
每组数据中，第一行是整数 n(1 <= n <= 10^5)，表示打印物件有几个部分。
接下来第二行包含 n 个用空格间隔的整数，每个整数 h_i(0 <= h_i <= 10^5)代表该部分需求的高度。

Output

对于每组数据，输出需要喷涂的最少次数，每个结果占据一行。

Sample Input

3
5
1 2 3 4 5
7
3 2 1 4 1 2 3
10
3 1 4 1 5 9 2 6 5 3

Sample Output

5
8
18

回答 2 - 错误解法

Based on the problem description, here's a possible solution in C++:

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> heights(n);
        for (int i = 0; i < n; i++) {
            cin >> heights[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || heights[i] > heights[i - 1]) {
                // start a new layer at index i
                int j = i + 1;
                while (j < n && heights[j] >= heights[j - 1]) {
                    j++;
                }
                ans += j - i;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Explanation:

We first read in the number of test cases T.

For each test case, we read in the number of parts n and the heights h_i of each part.

We then iterate through the parts and check if we need to start a new layer at the current part. We start a new layer if either it's the first part or the height of the current part is greater than the height of the previous part.

If we need to start a new layer, we iterate through the subsequent parts until we find a part whose height is less than the previous part. The number of parts between the start and end of the layer is the number of times we need to spray material for this layer.

We keep track of the total number of sprays ans and output it after processing all the parts for the current test case.

Note that this solution has a time complexity of O(n) per test case, so the overall time complexity is O(Tn), which should be fast enough to pass the given constraints.

回答 3 - 接近正确的解法

Here's the solution in C++:

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int T;
    cin >> T;
 
    while (T--) {
        int n;
        cin >> n;
 
        vector<int> heights(n);
        for (int i = 0; i < n; i++) {
            cin >> heights[i];
        }
 
        int prev_height = 0;
        int total_count = 0;
 
        for (int i = 0; i < n; i++) {
            if (heights[i] > prev_height) {
                total_count += heights[i] - prev_height;
            }
            prev_height = heights[i];
        }
 
        cout << total_count << endl;
    }
 
    return 0;
}

Explanation:

The problem requires us to find the minimum number of times the 3D printer needs to spray material on the object to reach the required heights for each part.

We can solve this problem by iterating through each part of the object and calculating the difference between the current height and the previous height. If the current height is greater than the previous height, we add the difference to the total count.

The variable prev_height keeps track of the height of the previous part, and the variable total_count keeps track of the total number of times we need to spray material.

We repeat this process for each test case and output the result for each test case.

Note: The time complexity of this solution is O(n), where n is the number of parts in the object.

提问 4 - 提示整型溢出

Consider a extreme case, if we have a object of 10^5 parts, which heights alternate between 0 and 10^5, then the 3D printer needs to spray 10^5 / 2 * 10^5 = 5 * 10^9 times, it'll overflows the range of int type.

回答 4 - 最终正确解法

You are correct. In extreme cases like the one you mentioned, the integer overflow can occur since the result of multiplying such large numbers exceeds the range of the integer data type.

To avoid this issue, we can use a 64-bit integer data type like long long instead of int to store the total_count variable. We can modify the code as follows:

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int T;
    cin >> T;
 
    while (T--) {
        int n;
        cin >> n;
 
        vector<int> heights(n);
        for (int i = 0; i < n; i++) {
            cin >> heights[i];
        }
 
        int prev_height = 0;
        long long total_count = 0;
 
        for (int i = 0; i < n; i++) {
            if (heights[i] > prev_height) {
                total_count += (long long)(heights[i] - prev_height);
            }
            prev_height = heights[i];
        }
 
        cout << total_count << endl;
    }
 
    return 0;
}

Now, the total_count variable is a long long type, and we cast the difference between the heights to long long before adding it to total_count. This ensures that the result is computed using a 64-bit integer and will not overflow.

Note: Some compilers may require the use of the LL suffix to create long long literals. For example, 10LL represents the long long value 10.