集训第四周（高效算法设计）M题 (扫描法)

原题：UVA11078

题意：给你一个数组，设a[]，求一个m=a[i]-a[j],m越大越好，而且i必须小于j

怎么求？排序？要求i小于j呢。枚举？只能说超时无上限。所以遍历一遍数组，设第一个被减数为a【0】，之后遇到比a【0】大的数就更新它，再拿这个被减数去减数组中的每一个元素，同时也要不断地更新这个m值。

#include"iostream"

#include"set"

#include"cstring"

#include"cstdio"

#include"algorithm"

using namespace std;

const int maxn=100000+10;

int a[maxn];

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        cin>>n;

        for(int i=0;i<n;i++)

        {

            cin>>a[i];

        }

        int x=a[0];

        int ans=-1;

        for(int i=1;i<n;i++)

          {

            ans=max(x-a[i],ans);

            x=max(a[i],x);

          }

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

集训第四周（高效算法设计）M题 (扫描法)

最新文章

热门文章