2022.8.20 网易笔试 长城数组 解题思路

/* 第二题 长城数组

   长城数组 1 9 1 9, 2 5 2 5 2 5
   非长城数组 2 3 1 2

   给定一个数组，每次可对其中任意一数执行加1操作
   问最少几次可以把它变成长城数组
*/

#include <iostream>
#include <vector>

#define PRINT_TMP_VECTOR // 输出中间过程数组

using namespace std;

template <typename T>
const ostream& operator<< (ostream &output, const vector<T> vec) {
    for (T i : vec)
        output << i << " ";
}

/**
 * GreatWallVector: 已经确认为长城数组的数组，长度至少为3，由调用者保证。
 * n: 要新添加的数
 */
int insert2GreatWall(vector<int> &GreatWallVector, int n) {
    // 将n添加到GreatWallVector的末尾，并调整为新的GreatWallVector
    int size = GreatWallVector.size();
    if (size < 2) { // 起始数组长度需要大于等于2
        return 0;
    }

    int large, small;
    if (GreatWallVector.at(0) > GreatWallVector.at(1)) {
        large = GreatWallVector.at(0);
        small = GreatWallVector.at(1);
    } else {
        large = GreatWallVector.at(1);
        small = GreatWallVector.at(0);
    }
    
    if (GreatWallVector.at(size - 1) == large) { // 结尾元素是大值
        if (n <= small) {
            GreatWallVector.push_back(small);
            return small - n;
        } else {//if (n <= large) {
            // 与下一情况操作一致
        //} else {
            int i = size - 2, res = 0;
            while (i >= 0) {
                GreatWallVector.at(i) = n;
                res += (n - small);
                i -= 2;
            }
            GreatWallVector.push_back(n);
            return res;
        }
    } else {
        /*
        if (n <= small) {
            GreatWallVector.push_back(large);
            return large - n;
        } else */ if (n <= large) { // 与上一条件操作一致
            GreatWallVector.push_back(large);
            return large - n;
        } else {
            int i = size - 2, res = 0;
            while (i >= 0) {
                GreatWallVector.at(i) = n;
                res += (n - large);
                i -= 2;
            }
            GreatWallVector.push_back(n);
            return res;
        }
    }
}

int Conv2GreatWall(vector<int> vec) {
    int n = vec.size(), res = 0;
    if (n < 3) // n == 1 || n == 2
        return res;

    vector<int> tmp(vec.begin(), vec.begin() + 2);

    // 对前三位预处理
    int start;
    if (tmp.at(0) == tmp.at(1)) { // 如果前两位数字相同，则需要考虑第三位数字的大小
        start = 3;
        tmp.push_back(vec.at(2));
        if (tmp.at(2) == tmp.at(0)) { // 第三个数字也相同
            res += 1;
            tmp.at(1)++; // 中间的数字加1
        } else if (tmp.at(2) > tmp.at(0)) { // 第三个数字大于前两位
            res += tmp.at(2) - tmp.at(0);
            tmp.at(0) = tmp.at(2); // 操作使首位等于第三位
        } else { // 第三个数字小于前两位
            tmp.at(0)++; // 首位加1
            res += (1 + tmp.at(0) - tmp.at(2));
            tmp.at(2) = tmp.at(0); // 让第三位等于首位
        }
    } else { // 如果前两位数字不相同，则不需要考虑第三位，第三位与后面统一处理
        start = 2;
    }
    if (n > start) {
        for (int i = start; i < n; ++i) {
            res += insert2GreatWall(tmp, vec.at(i));

#ifdef PRINT_TMP_VECTOR
            cout << "Current tmp vector is : ";
            cout << tmp;
            cout << endl;
#endif

        }
    }
    return res;
}

int main() {
    while (1) {

    int n, tmp;
    vector<int> vec;
    cout << "Input the size of vector: " << endl;
    cin >> n;
    cout << "Input the vector elements: " << endl;
    while (n-- > 0) {
        cin >> tmp;
        vec.push_back(tmp);
    }
    cout << Conv2GreatWall(vec) << endl;

    }
    return 0;
}