【Arc101D】Median of Medians

Source and Judge

Arc101D

Record

1h

Analysis

请先思考后再展开

题意:给一个长度为$n$的数列,把每个子串的中位数组成新的序列,求其中位数
做法1:枚举$l$和$r$,然后排序组成中位数,时间复杂度$O(n^2log_2n)$
做法2:枚举$now$,再枚举$l$和$r$,统计比它小的数量考虑其贡献,时间复杂度$O(n^3)$
正解(大小逻辑关系的运用不一定完全相同):

  1. 二分答案,难点在于如何判定问题:答案是否$\leq mid$
  2. 不难想到,可以判定 $\leq mid$ 的数字,$其贡献 \geq \lfloor \frac{n(n+1)}{4} \rfloor +1$ ,对于每个区间,用类似的思路,考虑是否会被”堵住“,$小于等于的数量>大于的数量$,用前缀和优化一下,$(a_r-a_{l-1})-(b_r-b_{l-1})>0$,为了方便,$c_{l-1}<c_r$
  3. 现在看起来复杂度是$O(n^2log_2n)$,但是显然可以用数据结构如树状数组优化,变成$O(nlog_2^2n)$

细节:爆int,一开始完全没注意到

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=110000;
int n;
int tr[2*MAXN];
int lowbit(int x) {return x&-x;}
void change(int d)
{
d+=MAXN;
while(d<2*MAXN) tr[d]++,d+=lowbit(d);
}
int sum(int d)
{
d+=MAXN;
int ans=0;
while(d>=1) ans+=tr[d],d-=lowbit(d);
return ans;
}
int a[MAXN],b[MAXN];
int c[MAXN];
typedef long long ll;//debug 爆int
bool check(int now)
{
for(int i=1;i<=n;i++) c[i]=c[i-1]+(a[i]<=now?1:-1);//1小于等于,-1大于
memset(tr,0,sizeof tr);//debug
change(c[0]);//debug
ll tot=0;//<=now的数,产生的贡献
for(int r=1;r<=n;r++)
{
//c[r]-c[l-1]>0 => c[l-1]<c[r] (l-1<r)
tot+=sum(c[r]-1);
change(c[r]);
}
return tot>=ll(n+1)*n/4+1;
}
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int l=1,r=1e9,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/f4a4.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%