HDU 5857 Median——模拟

HDU 5857 Median——模拟

#include #include #include using namespace std;int n,m;int a[100010];int l1,r1,l2,r2;int solve(int len){ if(r1 <= l2) { if(r1-l1+1 >= len) return a[l1+len-1]; else { len -= r1 - l1 + 1; return a[l2+len-1]; } } else { if(l2-l1 >= len) return a[l1+len-1]; else if(l2-l1+(r1-l2+1)*2 < len) { len -= r1-l1+1; return a[l2+len-1]; } else { len -= l2 - l1; if(len & 1) return a[l2+len/2]; else return a[l2+len/2-1]; } }}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); while(m--) { scanf("%d%d%d%d",&l1,&r1,&l2,&r2); if(l1 > l2) swap(l1,l2); if(r1 > r2) swap(r1,r2); int len = r1 - l1 + 1 + r2 - l2 + 1; if(len & 1) printf("%.1f\n",1.0*solve(len/2+1)); else printf("%.1f\n",0.5*solve(len/2)+0.5*solve(len/2+1)); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。