hdu5857Median

Median

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 2256 Accepted Submission(s): 542

Problem Description

There is a sorted sequence A of length n. Give you m queries, each one contains four integers, l1, r1, l2, r2. You should use the elements A[l1], A[l1+1] … A[r1-1], A[r1] and A[l2], A[l2+1] … A[r2-1], A[r2] to form a new sequence, and you need to find the median of the new sequence.

Input

First line contains a integer T, means the number of test cases. Each case begin with two integers n, m, means the length of the sequence and the number of queries. Each query contains two lines, first two integers l1, r1, next line two integers l2, r2, l1<=r1 and l2<=r2.

T is about 200.

For 90% of the data, n, m <= 100

For 10% of the data, n, m <= 100000

A[i] fits signed 32-bits int.

Output

For each query, output one line, the median of the query sequence, the answer should be accurate to one decimal point.

Sample Input

1
4 2
1 2 3 4
1 2
2 4
1 1
2 2
           

Sample Output

2.0
1.5
           

Author

BUPT

Source

2016 Multi-University Training Contest 10

题意: 就是要你在一个有序的数组里选两个区间[l1,r1]和[l2,r2]组成一个新的数组要你求中位数。

题解：

首先区间[l1,r1]和[l2,r2]有相交，包含和不相交三种关系！

不相交我们可以很简单搞出来！

相交又分为包含和相交一部分，我们可以把包含转变为部分相交，如下：（出现的先后顺序代表在序列的先后顺序）

[l1,__________,{l2,________,r1],_________r2}

1.讨论长度是奇数还是偶数

2.把你要找的下标为mid的数在原数组中找出来

3.如何找在新数组里位置为mid对应于原数组的位置，首先判断是否相交，不相交就很简单了，相交的话要分三个区间[l1,l2], [l2,r1]和[l2,r2]讨论

要注意的就是，我们确定了mid在哪个区间时，最好用左区间进行定位如：

l1+mid-1,或者l2+mid-1

如果用左区间r1或者r2定位注意不用再多减一次1了 我就是被这个坑了好久

比如你确定mid在【r1,r2】时，不能把mid减去【l1,l2】和[l2,r1]*2的和 然后返回a[r1+mid-1] ！！！(会出错，多减去了一个1)

AC代码：

#include<bits/stdc++.h>
using namespace std;
double a[100005];
int n,l1,r1,l2,r2;
double solve(int mid)
{
	int len1=r1-l1+1;
	int len2=r2-l2+1;
	if(r1<=l2)//不相交 
	{
		if(mid<=len1)
		{
			return a[l1+mid-1];
		}
		else
		{
			mid-=len1;
			return a[l2+mid-1];
		}
	}
	else//相交 
	{
		if(mid<=(l2-l1+1))//前[l1,l2] kjlk
		{
			return a[l1+mid-1];
		}
		//else if(mid>=(len1+len2-(r2-r1)))//后【r1,r2】 注意不用减1了 
		else if(mid>=len1+(r1-l2+1)) //后【r1,r2】 对！！！！ 
		{
			mid-=len1;
			/*mid-=(r1-l2);//再减1，就把r1位置减去了，下面就不能再-1了 
			return a[r1+mid-1];*/ 
			return a[l2+mid-1];
		}
		else//中间重叠部分 
		{
			mid-=(l2-l1+1);
			return a[l2+mid/2];
		}
	}//每次只能用l1或者l2定位(+mid)不能用r1或者r2+mid 左区间容易出错多减一个1 
}
int main(void)
{
	int q,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%lf",&a[i]);
		}
		while(q--)
		{
			scanf("%d %d",&l1,&r1);
			scanf("%d %d",&l2,&r2);
			if(l1>l2)
			swap(l1,l2);
			if(r1>r2)
			swap(r1,r2);
			int len1=r1-l1+1;
			int len2=r2-l2+1;
			// 都转化为 [l1,r1] [l2,r2] 或者 [l1, 【l2 ,r1 ],r2 】 
			if((len1+len2)%2==1)//奇数 
			{
				printf("%.1lf\n",solve((len1+len2+1)/2));
			}
			else
			{
				double a=solve((len1+len2)/2);
				double b=solve((len1+len2)/2+1);
				printf("%.1lf\n",(a+b)/2.0);
			}
		}
	}
	return 0;
}