首页 > 代码库 > POJ 2019 Cornfields (RMQ?反正我暴力了)
POJ 2019 Cornfields (RMQ?反正我暴力了)
【题意简述】:题目告诉我们很多数据,有N,表示这个农场的大小N*N,还有B,表示我们要测量的那个小正方形的大小B*B,还有K,代表我们要在这个N*N的农场上测几组数据。要测量的那个小正方形的左上角的坐标给你了,x和y。现在让我们求出在这个B*B的小正方形中最大的数值减去最小的数值结果是多少
【分析】:这本应是个二维的RMQ问题:
http://blog.csdn.net/u013749862/article/details/39008855
下面是别人用RMQ的解法:
http://kmplayer.iteye.com/blog/575725
接下来是我恶心 暴力的代码:
// 368K 891Ms 险过!! // 应该是用二维的RMQ,但是,暴力也过了 #include<iostream> #include<cstdio> using namespace std; int farm[251][251]; #define Max 251 #define Min 0 int N,B,K; int x,y; int main() { scanf("%d%d%d",&N,&B,&K); for(int i= 1 ;i<=N;i++) { for(int j =1;j<=N;j++) { scanf("%d",&farm[i][j]); } } while(K--) { scanf("%d%d",&x,&y); int max1 = Min; int min1 = Max; for(int i = x;i<x+B;i++) { for(int j = y;j<y+B;j++) { if(farm[i][j]>max1) max1 = farm[i][j]; if(farm[i][j]<min1) min1 = farm[i][j]; } } printf("%d\n",max1 - min1); } return 0; }
POJ 2019 Cornfields (RMQ?反正我暴力了)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。