华东交通大学2016年ACM“双基”程序设计竞赛 1008

Problem Description

halfyarn找你写个简单的题？好哒！给你n个整数,现在要求你选择两个位置的数，例如选择第pos_a个数a，和第pos_b个数b,给定ans=min(a,b)*abs(pos_a-pos_b),输出ans的最大值。

Input

第一行输入一个n代表有n个数，接下来的一行输入n个整数;
2<=n<=1e6;
1<=a,b<=1e6;
注意多组输入;

Output

ans的最大值;

Sample Input

4

1 2 2 2

Sample Output

Author

zhengjinke2123

解法：排序，然后从最大值开始遍历到最小，每到达一个数，把他当做最大值和最小值处理，j最大能取多少，最小能取多少，然后再遍历一次

5
2 3 1 5 4

排序后以及下标
1 2 3 4 5
3 1 2 5 4

比如1在3位置，它最大能取5，最小能取1，以此类推

5 5 5 4 4
1 1 2 4 4

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int Maxn=1e6+;

const LL Mod=1e9+;

int n;

int x[Maxn],y[Maxn];

struct P

{

    LL x,y;

} He[Maxn];

bool cmd(P a,P b)

{

    return a.x<b.x;

}

int main()

{

    int a;

    while(~scanf("%d",&n))

    {

        memset(x,,sizeof(x));

        memset(y,,sizeof(y));

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

        {

            scanf("%lld",&a);

            He[i].x=a;

            He[i].y=i;

        }

        sort(He+,He++n,cmd);

        x[n]=He[n].y,y[n]=He[n].y;

        LL Max=He[n].y,Min=He[n].y;

        for(int i=n-; i>=; i--)

        {

            if(Max>He[i].y)

            {

                x[i]=Max;

            }

            else

            {

                x[i]=x[i+];

                Max=He[i].y;

            }

            if(Min<He[i].y)

            {

                y[i]=Min;

                // cout<<

            }

            else

            {

                Min=He[i].y;

                y[i]=Min;

            }

        }

        LL M=-;

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

        {

            LL s=He[i].x;

            LL pos1=s*(LL)abs(He[i].y-x[i]);

            LL pos2=s*(LL)abs(He[i].y-y[i]);

            M=max({pos1,pos2,M});

        }

        printf("%lld\n",M);

    }

    return ;

}

巴特西