注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

bjfu-1044 水平差值  

2012-12-23 09:34:56|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

水平差值

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:62            测试通过:9

描述

计算机专业的实验课程或课程设计中经常会分组,既方便老师管理,又减轻老师的教学负担。可是如何分组才能达到最佳效果可不是那么容易的。实际分组一般会考虑到学生间的实际编程水平差异。(编程水平这东西真说不好,本题里我们粗略地假设学生的编程水平是固定的,可以用一个0-100之间的一个整数表示。)定义“水平差值”为选定的一组学生中水平最高学生和水平最低学生的水平值之差的绝对值。显然,“水平差值”太小或太大的分组都是不合理的。差值太小,组员间难以相互学习;差值太大,会影响某些组员的学习积极性。现在已知所有学生的编程水平数值,老师已经有若干分组方案,为了方便老师合理安排分组,请帮忙编写一个程序计算老师选定一组的学生的“水平差值”。

输入

输入包含多组测试数据,每组测试数据首先包含两个整数N和Q,分别表示该组测试数据中的学生总数和组数。然后是按顺序(例如学号顺序,从1开始编号)给出的N个学生的水平值,接下来是Q行,每行两个整数i和j,表示从第i个学生到第j个学生组成的一个分组。分组之间可能会有交叉或重复。(0<N<30000, 0<Q<100000)

输出

对于测试数据中的每一个分组,请在一行中输出其“水平差值”。

样例输入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出

6
3
0

————————————————————————————————————————————

线段树,直接模板飘过………这做模板使用

/*
* test1.cpp
*
* Created on: 2012-12-23
* Author: fudq
*/
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define MY_MIN 99999999
#define MY_MAX -99999999
typedef struct CNode{
int L,R;
int nMin,nMax;
CNode *pLeft,*pRight;
}CNode;
CNode Tree[500005];
int N,Q;
int nCount;
int CurMin,CurMax;
inline int min(int first,int second)
{
return first<second?first:second;
}

inline int max(int first,int second)
{
return first>second?first:second;
}

void BuildTree(CNode *pRoot,int L,int R)
{
pRoot->nMax=MY_MAX;
pRoot->nMin=MY_MIN;
pRoot->L=L;
pRoot->R=R;
if(L==R)
return ;
nCount++;
pRoot->pLeft=Tree+nCount;
nCount++;
pRoot->pRight=Tree+nCount;
int mid=(L+R)/2;
BuildTree(pRoot->pLeft,L,mid);
BuildTree(pRoot->pRight,mid+1,R);
}

void Insert(CNode *pRoot,int i,int v)
{
pRoot->nMax=max(pRoot->nMax,v);
pRoot->nMin=min(pRoot->nMin,v);
if(pRoot->L==pRoot->R)
return ;
int mid=(pRoot->L+pRoot->R)/2;
if(i<=mid)
Insert(pRoot->pLeft,i,v);
else
Insert(pRoot->pRight,i,v);
}

void Query(CNode *pRoot,int s,int e)
{
if(pRoot->nMax <= CurMax && pRoot->nMin >= CurMin)
return ;
if(s == pRoot->L && e == pRoot->R)
{
CurMax=max(CurMax,pRoot->nMax);
CurMin=min(CurMin,pRoot->nMin);
return ;
}
int mid=(pRoot->L+pRoot->R)/2;
if(e<=mid)
Query(pRoot->pLeft,s,e);
else if(s>mid)
Query(pRoot->pRight,s,e);
else
{
Query(pRoot->pLeft,s,mid);
Query(pRoot->pRight,mid+1,e);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int h,i,s,e,t;
while(scanf("%d %d",&N,&Q)!=EOF)
{
nCount=0;
BuildTree(Tree,1,N);
for(i=1;i<=N;i++)
{
scanf("%d",&h);
Insert(Tree,i,h);
}
for(i=0;i<Q;i++)
{
scanf("%d%d",&s,&e);
CurMin=MY_MIN;
CurMax=MY_MAX;
if(s>e)
{
t=s;
s=e;
e=t;
}
Query(Tree,s,e);
printf("%d\n",CurMax-CurMin);
}
}
return 0;
}


  评论这张
 
阅读(74)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018