关于判断单峰数组的几种方法

Problem - B - Codeforces

由题意可知若要保证对于数组A的所有排列有 f(a) <= f(b)，就要保证A数组是最优排列，也就是A数组中只能出现一个峰，只有这样才可以贪心地选择 [l, r] 范围内的数进行操作。

所以由此想到了一些判断单峰数组的方法：

方法一：

类似于双指针：从数组两端开始，对于左边若 a[i]>=a[i-1] , 左指针 ++；

                                                      对于右边若 a[i-1]>=a[i] , 右指针 --；

到最后如果左指针 >= 右指针(出现 l>r 是因为可能出现一段平整的数)，则一定为单峰数组；

int l = 1, r = n;
    for (int i = 1; i < n;)
    {
        if (a[i + 1] >= a[i])
        {
            i++;
            l = i;
        }
        else
            break;
    }

    for (int i = n; i > 1;)
    {
        if (a[i - 1] >= a[i])
        {
            i--;
            r = i;
        }
        else
            break;
    }

    if (l >= r)
    {
        cout << "YES" << endl;
        return;
    }
    else
    {
        cout << "NO" << endl;
        return;
    }

方法二：

用flag标记：(flag初始为false表示未出现峰) ,从前往后遍历数组，若出现 a[i] > a[i+1] 说明在i处已经出现过一个峰，此时将flag标记为true(表示出现过峰)，在这之后如果出现 a[i] < a[i+1] 的上升状态，说明在这之后必然要再出现一个峰

bool flag = false;
for (int i = 1; i < n; i++)
{
    if (!flag && a[i] > a[i + 1])
        flag = true;
    else if (flag && a[i] < a[i + 1])
    {
        cout << "NO" << endl;
        return;
    }
}
cout << "YES" << endl;
return;

方法三：

 当然不是我想到的

Submission #167245781 - Codeforces

既然是单峰，那么只有一次连续上升的机会，所以计算从头开始的上升增量，最后判断上升增量是否等于最高的峰(若只有一个峰，就可以保证上升增量严格等于最高峰)

看到这个思路直接ORZ！！

for (int i=1;i<=n;i++) 
{
    cin>>a[i];
    if (a[i]>a[i-1])
    {
        fa+=a[i]-a[i-1];
    }
    fb=max(fb,a[i]);
}
    if (fa==fb) cout<<"YES\n";
    else cout<<"NO\n";