题解 P7314 【[COCI2018-2019#3] Pismo】

· · 题解

1.题目分析

这道题首先可以发现，要让最大减最小最小，其实就是让最大值最大，最小值最小，于是我们考虑贪心，容易发现如下的性质：

\max{a_i,a_{i+1}\cdots a_j} \leq \max{a_i,a_{i+1}\cdots a_j,a_{j+1}} \min{a_i,a_{i+1}\cdots a_j} \geq \min{a_i,a_{i+1}\cdots a_j,a_{j+1}}

所以容易发现，区间长度越短越好，又因为 l<r ，所以区间长度最小为 2 。

AC Code

//By: Luogu@⚡炭治郎⚡(308854)
#include <bits/stdc++.h>

using namespace std;

int a[100100];
int n;
int ans=0x3f3f3f3f;

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<n;i++)
    {
        ans=min(ans,max(a[i],a[i+1])-min(a[i],a[i+1])); 
    } 

    cout<<ans;
}