首页 > 代码库 > CODEVS 2021中庸之道

CODEVS 2021中庸之道

2024-09-23 08:51:01   216人阅读

题目描述 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中庸之道


联系
我们