题意
给出一个长度为n的有序序列。给出m个询问,每个询问包括四个正整数l1,r1,l2,r2你用l1tor1的和l2tor2的元素来组成一个新的序列,然后找出这个序列的中位数。
分析
这是当时Spring Team Training D 的一道题,显而易见的模拟,我当时在场上写了190行。
赛后看了学长的代码后···orzzzzz!!
我当时分类的时候是把 “相交不包含(l2<r1&&r2>r1)”,和“包含(r2<r1)”作为两种情况来写。然而事实上,如果是包含,只需要swap(r1,r2)就可以按照相交不包含来处理了······
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream> using namespace std;
const int maxn=+;
int T,n,m,l1,r1,l2,r2;
int a[maxn];
int work(int x){
if(r1<l2){
if(x<=r1-l1+){
return a[l1+x-];
}
x=x-(r1-l1+);
return a[l2+x-];
}else{
int len=r1-l2+;
if(x<=r1-l1+-len+){
return a[l1+x-];
} if(x>r1-l1++len){
x=x-(r1-l1+);
return a[l2+x-];
}
x=x-(r1-l1+-len);
if(x%)
x=(x+)/;
else
x=x/;
return a[l1+(r1-l1+-len)+x-];
}
}
int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=m;i++){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(l1>l2){
swap(l1,l2);
swap(r1,r2);
}
if(r2<r1)
swap(r1,r2);
int len=r1-l1++r2-l2+;
if(len%){
double ans=(double)work((len+)/);
printf("%.1f\n",ans);
}else{
double ans=(double)work(len/)+(double)work(len/+);
printf("%.1f\n",ans/);
}
}
}
return ;
}