频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj_3264 Balanced Lineup
2012-07-31 15:36:56      个评论      
收藏   我要投稿
Balanced Lineup
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 23380
Accepted: 10882
Case Time Limit: 2000MS
 Description
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 agame of Ultimate Frisbee with some of the cows. To keep things simple, he willtake 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 inheight.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potentialgroups of cows and their heights (1 ≤ height ≤ 1,000,000). For eachgroup, he wants your help to determine the difference in height between theshortest 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 theheight 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 Binclusive.
Output
Lines 1..Q: Each line contains a single integerthat is a response to a reply and indicates the difference in height betweenthe 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
Source
USACO 2007 JanuarySilver
解题思路:
         这个题目可以用线段树来做,只有两个操作,第一个建立树,第二个查询线段区间即可。
代码:
 
#include <iostream> 
#include<cstdio> 
#include<cstring> 
#define N 50005 
#define Q 200005 
using namespace std; 
struct segment 

    int left; 
    int right; 
    int max; 
    int min; 
    int value; 
}; 
 
int n,q; 
int high; 
segment seg[N*4]; 
int max(int a,int b) 

    if(a>b) 
        return a; 
    return b; 

 
int min(int a,int b) 

    if(a<b) 
        return a; 
    return b; 

void update(int rt) 

    seg[rt].max=max(seg[rt*2].max,seg[rt*2+1].max); 
    seg[rt].min=min(seg[rt*2].min,seg[rt*2+1].min); 
 

//建树 
void buildTree(int l,int r,int rt) 

    seg[rt].left=l; 
    seg[rt].right=r; 
    if(l==r) 
    { 
        scanf("%d",&high); 
        seg[rt].max=seg[rt].min=high; 
        return; 
    } 
    int mid=(l+r)/2; 
    buildTree(l,mid,rt*2); 
    buildTree(mid+1,r,rt*2+1); 
    update(rt); 

 
//查询区间a到b中的最大差值 
int queryMax(int a,int b,int rt) 

    if(a==seg[rt].left && b==seg[rt].right) 
    { 
        return seg[rt].max; 
    } 
    int res=0; 
    int mid=(seg[rt].left+seg[rt].right)/2; 
    if(b<=mid) 
    { 
        res=max(res,queryMax(a,b,rt*2)); 
    } 
    else if(a>mid) 
    { 
        res=max(res,queryMax(a,b,rt*2+1)); 
    } 
    else 
    { 
        res=max(res,queryMax(a,mid,rt*2)); 
        res=max(res,queryMax(mid+1,b,rt*2+1)); 
    } 
    return res; 

 
int queryMin(int a,int b,int rt) 

    if(a==seg[rt].left && b==seg[rt].right) 
    { 
        return seg[rt].min; 
    } 
    int mid=(seg[rt].left+seg[rt].right)/2; 
    int res=999999999; 
    if(b<=mid) 
    { 
        res=min(res,queryMin(a,b,rt*2)); 
    } 
    else if(a>mid) 
    { 
        res=min(res,queryMin(a,b,rt*2+1)); 
    } 
    else 
    { 
        res=min(res,queryMin(a,mid,rt*2)); 
        res=min(res,queryMin(mid+1,b,rt*2+1)); 
    } 
    return res; 
     

 
int main() 

 
    int a,b; 
 
    scanf("%d%d",&n,&q); 
    buildTree(1,n,1); 
    while(q--) 
    { 
        scanf("%d%d",&a,&b); 
        int max = queryMax(a,b,1); 
        int min= queryMin(a,b,1); 
        int val=max-min; 
        printf("%d\n",val); 
    } 
    return 0; 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:初学KMP Power Strings hoj
下一篇:poj1410巧妙变成直线与线段相交
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站