POJ 3264 Balanced Lineup //简单线段树

港控/mmm° 2022-09-20 15:24 139阅读 0赞

<table style="font-family:Simsun"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      Balanced Lineup 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;33405</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;15671</td> 
       </tr> 
       <tr> 
        <td colspan="3" align="center" style="color:rgb(14,173,0)"><strong>Case Time Limit:</strong>&nbsp;2000MS</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Description</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <p>For the daily milking, Farmer John's&nbsp;<em>N</em>&nbsp;cows (1 ≤&nbsp;<em>N</em>&nbsp;≤ 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.</p> 
     <p>Farmer John has made a list of&nbsp;<em>Q</em>&nbsp;(1 ≤&nbsp;<em>Q</em>&nbsp;≤ 200,000) potential groups of cows and their heights (1 ≤&nbsp;<em>height</em>&nbsp;≤ 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.</p> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Input</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Line 1: Two space-separated integers,&nbsp; 
     <em>N</em>&nbsp;and&nbsp; 
     <em>Q</em>.&nbsp; 
     <br> Lines 2.. 
     <em>N</em>+1: Line&nbsp; 
     <em>i</em>+1 contains a single integer that is the height of cow&nbsp; 
     <em>i</em>&nbsp; 
     <br> Lines&nbsp; 
     <em>N</em>+2.. 
     <em>N</em>+ 
     <em>Q</em>+1: Two integers&nbsp; 
     <em>A</em>&nbsp;and&nbsp; 
     <em>B</em>&nbsp;(1 ≤&nbsp; 
     <em>A</em>&nbsp;≤&nbsp; 
     <em>B</em>&nbsp;≤&nbsp; 
     <em>N</em>), representing the range of cows from&nbsp; 
     <em>A</em>&nbsp;to&nbsp; 
     <em>B</em>&nbsp;inclusive. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Output</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Lines 1.. 
     <em>Q</em>: 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. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Input</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">6 3
1
7
3
4
2
5
1 5
4 6
2 2</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Output</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">6
3
0</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Source</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=USACO+2007+January+Silver" style="text-decoration:none" rel="nofollow">USACO 2007 January Silver</a> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][]\] \[Go Back\] \[[Status][]\] \[[Discuss][]\]

![home.gif][][Home Page][] ![goback.gif][]Go Back ![top.gif][][To top][]

#include <stdio.h>
    
    struct node 
    {
    	int l, r;
    	int max, min;
    }tree[200005];
    int h[50004];
    int max, min;
    
    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 build(int l, int r, int root)  //建树
    {
    	int mid;
    
    	tree[root].l = l;		//将区间位置 赋给 树
    	tree[root].r = r;
    
    	if(l==r)
    	{
    		tree[root].max = tree[root].min = h[l];//当叶子结点区间长度为1时，赋值
    		return ;
    	}
    	mid = (l + r)>>1;		//除2
    	build(l, mid, 2*root);  	//建立左子树
    	build(mid+1, r, 2*root+1);  //建立右子树
    	
    	tree[root].max = MAX(tree[root*2].max, tree[root*2+1].max);//当前结点的最大最小值等于他的 左子树与右子树 中的最大最小值。
    	tree[root].min = MIN(tree[root*2].min, tree[root*2+1].min);
    }
    void findmax(int l, int r, int root)
    {
    	int mid;
    	if(tree[root].l==l && tree[root].r==r)//当查找的区间与结点区间吻合时，这区间的最大最小值就是这个结点的最大最小值。
    	{
    		max = MAX(max, tree[root].max);
    		min = MIN(min, tree[root].min);
    		return ;
    	}
    	mid = (tree[root].l + tree[root].r)>>1;
    	if(mid >= r)     //当查找的区间在此结点的 左子树时；
    		findmax(l, r, root*2);
    	else if(mid < l) //当查找的区间在此结点的 右子树时；
    		findmax(l, r, root*2+1);
    	else			//当查找的区间横跨此结点的 左右子树时；
    	{
    		findmax(l, mid, root*2);
    		findmax(mid+1, r, root*2+1);
    	}
    }
    
    int main()
    {
    	int n, q;
    	int l, r;
    	int i;
    
    	scanf("%d%d", &n, &q);
    	for(i=1; i<=n; i++)
    		scanf("%d", &h[i]);
    	build(1, n, 1);		//从第1个结点开始建树。
    
    	while(q--)
    	{
    		scanf("%d%d", &l, &r);
    		max = -0xfffff;			//赋初值
    		min = 0xfffff;
    		findmax(l, r, 1);	
    
    		printf("%d\n", max-min);
    	}
    
    	return 0;
    }

[Submit]: http://poj.org/submit?problem_id=3264
[Status]: http://poj.org/problemstatus?problem_id=3264
[Discuss]: http://poj.org/bbs?problem_id=3264
[home.gif]: http://poj.org/images/home.gif
[Home Page]: http://poj.org/
[goback.gif]: http://poj.org/images/goback.gif
[top.gif]: /images/20220823/7b1daea5780f4102bb769b6c5673a848.png
[To top]: http://poj.org/problem?id=3264#top