Balanced Lineup
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.
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 C++版本一
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
int t,n,q;
long tree1[50010<<2];
long tree2[50010<<2];
long a[50010];
void PushUp(int rt){
tree1[rt] =max(tree1[rt*2] , tree1[rt*2+1]) ; ///区间和的更新操作
tree2[rt] =min(tree2[rt*2] , tree2[rt*2+1]) ;
}
void Build(int l,int r,int rt){
// l,r 代表的是这个区间内的左端点 和 右端点， rt代表的是 [l,r] 这个区间内的值是存在哪一个位置的。
if(l==r){
//scanf("%d",&tree[rt]);
tree1[rt] = a[l];
tree2[rt] = a[l];
return;
}
int m=(l+r)/2;// 对于区间区分，我们一般将m点划入左半边区间
Build(l,m,rt*2);
Build(m+1,r,rt*2+1);
PushUp(rt); // PushUp 函数是通过2个子节点来更新现在这个节点的状态， 对于不同的要求需要不同的写法。
}
long MAXQuery(int l,int r,int rt,int L,int R){// [L,R]为查询区间
if(L <= l && r <= R){
return tree1[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
}
int m=(l+r)/2;
long res=0;
if(L<=m) res=max(res,MAXQuery(l,m,rt*2,L,R));//左边有一部分需要查询的区域。
if(m<R) res=max(res,MAXQuery(m+1,r,rt*2+1,L,R));//右边有一部分。
return res;
}
long MINQuery(int l,int r,int rt,int L,int R){// [L,R]为查询区间
if(L <= l && r <= R){
return tree2[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
}
int m=(l+r)/2;
long res=0x3f3f3f;
if(L<=m) res=min(res,MINQuery(l,m,rt*2,L,R));//左边有一部分需要查询的区域。
if(m<R) res=min(res,MINQuery(m+1,r,rt*2+1,L,R));//右边有一部分。
return res;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++)
scanf("%ld", &a[i]);
Build(1,n,1);
int a,b;
while(q--){
scanf("%d%d",&a,&b);
cout << MAXQuery(1,n,1,a,b)-MINQuery(1,n,1,a,b) << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <map>
#include <stdlib.h>
#include <queue>
#include <functional>
using namespace std;
const int MAX = 5e4+10;
const double eps = 1e-8;
const double PI = acos(-1.0);
struct node
{
int minn, maxx;
}lxt[MAX*6];
int a[MAX];
int n, q, r, l;
void build(int l, int r, int pos)
{
if(l==r)
{
scanf("%d", &lxt[pos].minn);
lxt[pos].maxx = lxt[pos].minn;
}
else
{
build(l, (l+r)/2, pos*2);
build((l+r)/2+1, r, pos*2+1);
lxt[pos].maxx = max(lxt[pos*2+1].maxx, lxt[pos*2].maxx);
lxt[pos].minn = min(lxt[pos*2+1].minn, lxt[pos*2].minn);
}
//printf("%d %d %d %d \n", l, r, lxt[pos].maxx, lxt[pos].minn);
}
int check1(int l, int r, int ll, int rr, int pos)
{
if(ll==l&&rr==r)return lxt[pos].maxx;
else
{
int mid = (ll+rr)/2;
if(r<=rr&&l>mid)return check1(l,r,mid+1, rr, pos*2+1);
else if(r<=mid&&l>=ll)return check1(l,r,ll,mid,pos*2);
else
{
return max(check1(l, mid, ll, mid, pos*2),check1(mid+1, r, mid+1, rr, pos*2+1));
}
}
}
int check2(int l, int r, int ll, int rr, int pos)
{
if(ll==l&&rr==r)return lxt[pos].minn;
else
{
int mid = (ll+rr)/2;
if(r<=rr&&l>mid)return check2(l,r,mid+1, rr, pos*2+1);
else if(r<=mid&&l>=ll)return check2(l,r,ll,mid,pos*2);
else
{
return min(check2(l, mid, ll, mid, pos*2),check2(mid+1, r, mid+1, rr, pos*2+1));
}
}
}
int main()
{
while(~scanf("%d%d", &n, &q))
{
build(1, n, 1);
//for(int i =1; i<=50; ++i)
//printf("%d %d\n", lxt[i].maxx, lxt[i].minn);
while(q--)
{
scanf("%d%d", &l, &r);
if(l>r)swap(l,r);
printf("%d\n", check1(l,r,1,n,1)-check2(l,r,1,n,1));
}
}
return 0;
}
C++版本三
题目大意：
一个农夫有N头牛，每头牛的高度不同，我们需要找出最高的牛和最低的牛的高度差。
解题思路：
我是用RMQ写的。
N为50000，Q为200000，如果我们暴力的话，需要50000*200000=10000000000，需要25s左右.所以我们需要高效的算法，而RMQ正好解决的就是区间最值问题，复杂度为nlogn，这样就可以了。
另外还可以用线段树，因为线段树的别名就是区间树。segment tree
#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 50005;
int FMAX[N][20], FMIN[N][20];
void RMQ(int n)
{
for(int j = 1; j != 20; ++j)
{
for(int i = 1; i <= n; ++i)
{
if(i + (1 << j) - 1 <= n)
{
FMAX[i][j] = max(FMAX[i][j - 1], FMAX[i + (1 << (j - 1))][j - 1]);
FMIN[i][j] = min(FMIN[i][j - 1], FMIN[i + (1 << (j - 1))][j - 1]);
}
}
}
}
int main()
{
int num, query;
int a, b;
while(scanf("%d %d", &num, &query) != EOF)
{
for(int i = 1; i <= num; ++i)
{
scanf("%d", &FMAX[i][0]);
FMIN[i][0] = FMAX[i][0];
}
RMQ(num);
while(query--)
{
scanf("%d%d", &a, &b);
int k = (int)(log(b - a + 1.0) / log(2.0));
int maxsum = max(FMAX[a][k], FMAX[b - (1 << k) + 1][k]);
int minsum = min(FMIN[a][k], FMIN[b - (1 << k) + 1][k]);
printf("%d\n", maxsum - minsum);
}
}
return 0;
}
C++版本四
这道题目的确出的很好
首先是题意的转换，怎么去寻找最大的距离
那么我们看例子
7 3
7
6
7
2
1
4
2
转化为2进制
111
110
111
010
001
100
010
逐个累加
111
221
332
342
343
443
453
分别减去最右边的数
000
110《----
110
120
010
110《----
120
就可以发现是2和6是最远的相同数字，那么只用6-2=4即可算出答案
那到底为什么这么做就对了呢？
为什么两个数一样就得到了正确解了呢。
可以这么理解，当两个数相同时，说明在这两个数之间出现的数在每个特征上出现的数目相同，否则是不会两个数相同的。因为只有最右边的那个数增加了和左边所有的数增加的数字相同，他们才会减去最右边的数，出现相同
接着可以用HASH，也可以用MAP，我觉得不需要用MULTIMAP，因为只需要记录每个数字形式出现的最早时期即可。
注意给HASH函数加上0000000000这种情况
#include<stdio.h>
#include<string.h>
const int N=100100;
const int prime=100003;
int sum[N][32],c[N][32];
int hash[N];
int hashcode(int* v,int k)
{
int p;
for(int i=1;i<=k;i++) p=((p<<2)+(v[i]>>4))^(v[i]<<10);
p=p%prime;
if(p<0) p=p+prime;
return p;
}
int main()
{
//freopen("lineup.10.in","r",stdin);
//freopen("out.txt","w",stdout);
int n,k;
int ans=0;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(sum,0,sizeof(sum));
memset(hash,-1,sizeof(hash));
memset(c,0,sizeof(c));
hash[hashcode(c[0],k)]=0;
ans=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
for(int j=1;j<=k;j++)
{
sum[i][j]=sum[i-1][j]+x%2;
c[i][j]=sum[i][j]-sum[i][1];
x=x>>1;
}
int p=hashcode(c[i],k);
while(hash[p]!=-1)
{
int j;
for(j=1;j<=k;j++)
if(c[i][j]!=c[hash[p]][j]) break;
if(j==k+1)
{
if(i-hash[p]>ans) ans=i-hash[p];
break;
}
p++;
}
if(hash[p]==-1) hash[p]=i;
}
printf("%d/n",ans);
}
return 0;
}
C++版本五
题解：ST表
https://blog.csdn.net/weixin_43272781/article/details/88386252
/*
*@Author: STZG
*@Language: C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
ll maxl[N][21],minl[N][21];
void RMQ_ST(){
for(int i=0;i<20;i++){
for(int j=1;j+(1<<i)<=n;j++){
maxl[j][i+1] = max(maxl[j][i], maxl[j+(1<<i)][i]);
minl[j][i+1] = min(minl[j][i], minl[j+(1<<i)][i]);
}
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//scanf("%d",&n);
//scanf("%d",&t);
//while(t--){}
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++){
scanf("%d", &k);
maxl[i][0]=minl[i][0]=k;
}
int a,b;
RMQ_ST();
while(q--){
scanf("%d%d",&a,&b);
k=log2(b-a+1);
cout<<max(maxl[a][k],maxl[b-(1<<k)+1][k])-min(minl[a][k],minl[b-(1<<k)+1][k])<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}
查看2道真题和解析
良品铺子工作强度 8人发布