P2311 loidc,想想看 题解

· · 题解

看到题解区的大佬们有用线段树的，有用单调队列的，只会暴力的本蒟蒻大受震撼。

题目简化：

给定长度为 n 的数组 a ，求 a_x 和 a_y 之间最大的数的位置。

思路：

首先，读入，不必多说。

然后，我们用maxn表示最大数的值，用 ans 表示最大数的位置。遍历 a_x 和 a_y 之间的所有数。如果 a_i 比maxn大，就把maxn替换为 a_i ，把ans替换为 i。

最后，输出ans，就得到答案了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[100005],x,y;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    while(m--)//循环m次
    {
        cin>>x>>y;
        int maxn=-1,ans=0;//maxn为最大数的值，ans为最大数的位置
        for(int i=x;i<=y;i++)//从x遍历到y
        {
            if(a[i]>maxn)
            {
                maxn=a[i];ans=i;
            }//如果a[i]大于当前最大数的值，就把最大值替换为a[i]，位置替换成i
        }
        cout<<ans<<endl;
    }
    return 0;
}