补题：消失的高数试卷（牛客）
之前此题一直存在的问题是一直超时，后来看到一种方法，是用了打表法。 先定义两个数组a,b，在输入数组p后，一个数组a从1开始，到n结束。逐个比较a[i-1]与p[i]的大小，如果a[i-1]小于p[i]，就让a[i]=p[i]，否则a[i]=a[i-1]。这样做可以让一个区域内的最大值成为右边数列中下一个比他大的数。同样，如果b[i+1]小于p[i],就让b[i]=p[i],b[i+1]>p[i]，就让b[i]=b[i+1]。 上面说的打表法，是在上面步骤完成后，再读取l和r,从数列中删掉序号l到r之间的数，比较a[l-1]和b[r+1]的值，取最大的，即为剩下数列中最大的值。因为删掉l和r之间的数后， 代码如下：
#include<bits/stdc++.h>
using namespace std;
int a[1000010],b[1000010],p[100010];
int main()
{
int n,m,i;
a[0]=0;
scanf("%d %d",&n,&m);
b[n+1]=0;
for( i=1;i<=n;i++){
scanf("%d",&p[i]);
}
for(i=1;i<=n;i++){
if(a[i-1]<p[i])a[i]=p[i];
else a[i]=a[i-1];
}
for( i=n;i>0;i--){
if(b[i+1]<p[i])b[i]=p[i];
else b[i]=b[i+1];
}
int j,k;
for(i=m;i>0;i--){
scanf("%d %d",&j,&k);
int o=max(a[j-1],b[k+1]);
printf("%d\n",o);
} return 0;
}
阿里巴巴开奖92人在聊
，
查看19道真题和解析
