B. Balanced Lineup
2024-09-03 08:04:47
B. Balanced Lineup
Time Limit: 5000ms
Case Time Limit: 5000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.
Input
Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Output
Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0 解题:RMQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
int mn[][],mx[][],d[];
int main(){
int n,m,x,y,i,j;
while(~scanf("%d %d",&n,&m)){
for(i = ; i < n; i++){
scanf("%d",d+i);
}
memset(mn,,sizeof(mn));
memset(mx,,sizeof(mx));
for(i = n-; i >= ; i--){
mn[i][] = mx[i][] = d[i];
for(j = ; i+(<<j)- < n; j++){
mn[i][j] = min(mn[i][j-],mn[i+(<<(j-))][j-]);
mx[i][j] = max(mx[i][j-],mx[i+(<<(j-))][j-]);
}
}
for(i = ; i < m; i++){
scanf("%d %d",&x,&y);
if(x > y) swap(x,y);
int r = y - x + ;
r = log2(r);
int theMax,theMin;
theMax = max(mx[x-][r],mx[y-(<<r)][r]);
theMin = min(mn[x-][r],mn[y-(<<r)][r]);
printf("%d\n",theMax-theMin);
}
}
return ;
}
最新文章
- 【转】Oracle 执行计划(Explain Plan) 说明
- int.Parse()之异常
- 关于SQL储存过程中输出多行数据
- securityCRT mongoDB 命令行删除(backspace/delete)无效问题
- communicate with other processes, regardless of where they are running
- ADO.NET 拾遗
- 核心概念 &mdash;&mdash; 门面(Facades)
- DIV 清除样式浮动万能代码
- Delphi WebBrowser控件的使用(大全 good)
- ORACLE多表关联UPDATE 语句
- 权威指南之脚本化jquery
- VB6.0数据库开发五个实例——罗列的总结
- jenkins 用户名密码忘记
- Mysql求百分比
- adb命令安装apk 来学习吧
- 简单文本悬浮div提示效果
- bzoj 3224: Tyvj 1728 普通平衡树 &;&; loj 104 普通平衡树 (splay树)
- Effective STL 学习笔记:19 ~ 20
- Mutex 的正确打开方式
- Java并发--volatile详情