谁说暴力铁定拿低分！！！
本题数据非常弱，大模拟90分，除了最后一个点TLE了，其他都能很快AC，如果真是到了赛场上，没时间做这个题或者觉得代码难度较高的话，暴力的解法不妨一试！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,a[200100];
int (){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
int ans=a[x];
for(int j=x;j<=y;j++) ans=min(a[j],ans);
printf("%d ",ans);
}
return 0;
}
|
下面放一下ST表实现的正解，这是很标准的RMQ问题~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
int st[100010][22];
int st_init(){
for(int j=1;1<<j<=m;j++)
for(int i=1;i+(1<<j)-1<=m;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int st_ask(int l,int r){
int k=log2(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
int (){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) scanf("%d",&st[i][0]);
st_init();
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d ",st_ask(x,y));
}
return 0;
}
|
近期评论