算法-每天一道题（18）-发奖金

狐进行了一次黑客马拉松大赛，全公司一共分为了N个组，每组一个房间排成一排开始比赛，比赛结束后没有公布成绩，但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩，比赛结束之后要发奖金，以1w为单位，每个组都至少会发1w的奖金，另外，如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金，就会不满意，作为比赛的组织方，根据成绩计算出至少需要发多少奖金才能让所有的组满意。

输入描述:

每组数据先输入N，然后N行输入N个正整数，每个数表示每个组的比赛成绩。

输出描述:

输出至少需要多少w的奖金

输入例子:

10

20

32

12

32

45

11

21

31

41

33

输出例子:

20

C++

#include <iostream>
#include <vector>
#define MAX 9999
using namespace std;

// 往左移动的时候回倒回来
void modified_min(int min, vector<int> &v, vector<int> grade, int n)
{
    // 回倒的时候，如果回倒grade大于本身的grade，那么回倒grade也就应该+1
    // 但是如果回倒grade本身就是很大的，本身grade+1之后仍然小于回倒grade，那么就终止
    for (int i = min; i<n - 1; i++)
    {
        v[i] = v[i] + 1;
        // 本身grade+1之后仍然小于回倒grade，终止：因为此回倒grade不是产生本身grade的原因
        if (v[i] < v[i + 1])
            break;
        if (grade[i] > grade[i + 1])
            break;
    }
}

// 往右移动的时候回倒回来，同理向左移动
void modified_max(int max, vector<int> &v, vector<int> grade, int n)
{
    for (int i = max; i>0; i--)
    {
        v[i] = v[i] + 1;
        if (v[i] < v[i - 1])
            break;
        if (grade[i] > grade[i - 1])
            break;
    }
}

int main(int argc, char const *argv[])
{
    int n;
    int grade_min = MAX;
    int min = 0;
    int temp;
    int result = 0;
    while (cin >> n)
    {
        vector<int> v(n); // 奖金
        vector<int> grade(n); // 成绩

        for (int i = 0; i<n; i++)
        {
            cin >> temp;
            grade[i] = temp;
            if (grade[i] < grade_min)
            {
                grade_min = grade[i];
                min = i;
            }
        }
        v[min] = 1;

        // 向左移动
        for (int i = min; i>0; i--)
        {
            if (grade[i - 1] > grade[i])
                v[i - 1] = v[i] + 1;
            else if (grade[i - 1] == grade[i])
                v[i - 1] = 1;
            else
            {
                v[i - 1] = v[i] - 1;
                if (v[i - 1] < 1)
                    modified_min(i - 1, v, grade, n);
                v[i - 1] = 1;
            }
        }

        // 向右移动
        for (int i = min; i<n - 1; i++)
        {
            if (grade[i + 1] > grade[i])
                v[i + 1] = v[i] + 1;
            else if (grade[i + 1] == grade[i])
                v[i + 1] = 1;
            else
            {
                v[i + 1] = v[i] - 1;
                if (v[i + 1] < 1)
                    modified_max(i + 1, v, grade, n);
                v[i + 1] = 1;
            }
        }
        for (int i = 0; i<n; i++)
            result = v[i] + result;
        cout << result << endl;
        grade_min = MAX;
        v.clear();
        grade.clear();
        result = 0;
    }
}

/*
解题思路：

找到最小的成绩grade的角标min，然后向左和向右移动，
向左移动：
如果grade[min-1] > grade[min], 那么v[min-1] = v[min] + 1
如果grade[min-1] == grade[min]，那么v[min-1] = 1

如果grade[min-1] < grade[min]，
那么v[min-1] = 1，但是可能v[min] = 1，也就是min-1的成绩小于min，但是奖金却和min相等。
所以就应该回倒回去，把以前的+1.
所以v[min-1] = 1, 并且v[min] = v[min] + 1，(如果可能v[min+1]和v[min]相等且成绩大于min的话，
那么v[min+1] = v[min+1] + 1, 依次类推..
但是回倒回去的时候，可能遇见:
本身v的grade+1之后仍然小于回倒grade. 此时终止：因为此回倒grade不是产生本身grade的原因。
其中有很多细节，详见代码。
*/