情之所至,甘之如饴

谁说暴力铁定拿低分!!!

本题数据非常弱,大模拟90分,除了最后一个点TLE了,其他都能很快AC,如果真是到了赛场上,没时间做这个题或者觉得代码难度较高的话,暴力的解法不妨一试!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,a[200100];
int main(){
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 <iostream>
#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 main(){
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;
}

 评论



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k