第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 C 上进的凡凡

题目描述：

凡凡是一个上进的人，他的人生没有下坡路，他也讨厌带有”下坡路“的东西。

所以，对于凡凡来说，只有非降序的数组才是nice的（如：1，2，2，3，4，5，5）；若数组元素个数为1，也满足非降序，也是nice的。

现在有一个长度为n的数组，凡凡想知道它的子数组中有多少个数组是nice的。

你能帮帮他吗？

对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组b获得数组a，则称数组a是数组b的子数组。（子数组包含原数组，但不包含空串）

输入描述：

第一行输入一个整数n(1≤n≤10^5)，表示数组的长度。

第二行包含n个空格分隔的整数a1,a2,.,an(0≤ai≤10^9)，为数组的元素。

输出描述：

输出给定数组的子数组中是nice数组的个数。（注意使用long long）

示例：

输入：

5
1 2 3 4 5

输出：

15

思考：

题意是要找单调不减的子数组的个数，我首先想到的是for遍历...看了看数据大小，八成是不可行。

然后我就想，如何用快速的方式去描述数组的单调不减性呢，比较两个数的大小很好比较，然后是不是可以通过比较两个数的大小进而描述单调不减数组的存在个数呢。

于是我又定一个一个等大小的数组，存放什么呢，存放以该元素结束的单调不减数组的个数，这样如果对于一个元素大于等于前一个元素，就可以把以前一个元素结束的数组个数传到该元素上，并让数组个数++，因为现在又多了一个。

然后以此类推，时间复杂度就很小了，代码如下：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

int main()
{
    long long n;
    long long a[100005];
    long long aj[100005];
    long long ans;
    int judge = 1;

    memset(a,0,sizeof(a));
    memset(aj,0,sizeof(aj));
    cin>>n;
    ans = n;
    for(long long i = 0;i < n;i++)
    {
        cin>>a[i];
    }
    for(long long i = 1;i < n;i++)
    {
        if(a[i] >= a[i-1])
        {
            aj[i] = judge;
            judge++;
        }
        else
        {
            judge = 1;
        }
        ans += aj[i];
    }

    cout<<ans<<endl;
    return 0;
}

34ms