USACO Balanced Lineup
poj 3264
http://poj.org/problem?id=3264
洛谷 P2880
https://www.luogu.org/problemnew/show/P2880
题目描述
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.
一个农夫有N头牛,每头牛的高度不同,我们需要找出最高的牛和最低的牛的高度差。
输入输出格式
输入格式:
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 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.
输入输出样例
6 3
1
7
3
4
2
5
1 5
4 6
2 2
6
3
0 RMQ的裸题,直接用ST算法AC就可以。
跑一遍最大值再来一遍最小值。
AC Code:
#include<cstdio>
#include<algorithm>
using namespace std;
int n,q;
int lg[];
int f[][],p[][];
int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
{
scanf("%d",&f[i][]);
p[i][]=f[i][];
}
for(int i=;i<=n;i++)
lg[i]=lg[i>>]+;
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<=n;i++)
{
f[i][j]=max(f[i][j-],f[i+(<<(j-))][j-]);
p[i][j]=min(p[i][j-],p[i+(<<(j-))][j-]);
}
for(int i=;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int k=lg[y-x+];
printf("%d\n",max(f[x][k],f[y-(<<k)+][k])-min(p[x][k],p[y-(<<k)+][k]));
}
return ;
}
最新文章
- python2与python3在windows下共存
- 反射 实现不同模型相同属性赋值 第二集(automapper)
- sublime package
- ajax GET和POST请求web api 的几种方式
- android 在EditText中显示表情图片
- android 自定义view之 TypeArray
- libeXosip2(2) -- General purpose API.
- plsql在64位机器下读取tnsname.ora 及oracle_home异常的解决办法
- XNA 4.0 环境搭建和 Hello World,Windows Phone 游戏开发
- MSPointerEvent属性
- 程序导致IIS服务器应用程序池停止
- Mysql加锁过程详解(2)-关于mysql 幻读理解
- [HNOI/AHOI2018]转盘
- Android勒索软件研究报告
- gene Ontology (基因本体论)
- install docker swarm on centos
- RSD 直观介绍
- js 把数组对象按照某个属性进行排序
- VIM复制粘贴大全[转]
- Spring 单例 httprequest 线程安全