首页 > 代码库 > CODEVS 2021中庸之道
CODEVS 2021中庸之道
题目描述 Description
给定一个长度为N的序列,有Q次询问,每次询问区间[L,R]的中位数。
数据保证序列中任意两个数不相同,且询问的所有区间长度为奇数。
输入描述 Input Description
第一行为N,Q。
第二行N个数表示序列。
接下来Q行,每行为L,R,表示一次询问。
输出描述 Output Description
输出Q行,对应每次询问的中位数。
样例输入 Sample Input
5 3
1 4 8 16 2
1 5
3 5
3 3
样例输出 Sample Output
4
8
8
数据范围及提示 Data Size & Hint
40%的数据,N,Q≤100;
70%的数据,N≤100;
100%的数据,N≤1000,Q≤100000,序列中的元素为1到10^9之间的整数。
首先放上常规做法:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int n,q; 6 int num[1001],a[1001]; 7 int main() 8 { 9 scanf("%d%d",&n,&q); 10 for(int i=1;i<=n;i++) 11 scanf("%d",&num[i]); 12 for(int i=1;i<=q;i++) 13 { 14 int l,r,head=0; 15 scanf("%d%d",&l,&r); 16 for(int j=l;j<=r;j++) 17 a[++head]=num[j]; 18 sort(a+1,a+r-l+2); 19 int mid=(r-l+2)/2; 20 printf("%d\n",a[mid]); 21 } 22 return 0; 23 }
思路很简单,用一个数组存储索要询问的区间,然后进行排序,中间值就是的答案了。
不过这么做会只会拿90分(剩下那一个T了,大家可以试一下用cin和cout进行输入输出)。
将下来,正解,用二分就好了:
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,q,L,R; 5 int num[10010],s[10010]; 6 void kp(int x,int y) 7 { 8 int l=x,r=y,mid=num[(l+r)/2]; 9 while(l<=r) 10 { 11 while(num[l]<mid)l++; 12 while(num[r]>mid)r--; 13 if(l<=r) 14 { 15 swap(num[l],num[r]); 16 l++;r--; 17 } 18 } 19 if(l<y && l<=(L+R)/2)kp(l,y); 20 if(x<r && r>=(L+R)/2)kp(x,r); 21 } 22 int main() 23 { 24 cin>>n>>q; 25 for(int i=1;i<=n;i++) 26 { 27 cin>>num[i]; 28 s[i]=num[i]; 29 } 30 for(int i=1;i<=q;i++) 31 { 32 cin>>L>>R; 33 int mid=(L+R)/2; 34 kp(L,R); 35 cout<<num[mid]<<endl; 36 for(int i=1;i<=n;i++) 37 //在处理上一组数据时num的值已经改变,所以另找一个数组存放初始值 38 num[i]=s[i]; 39 } 40 return 0; 41 }
CODEVS 2021中庸之道
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。