牛客 NOIp模拟1 T1 中位数 解题报告
2024-10-12 23:15:38
中位数
题目描述
小\(N\)得到了一个非常神奇的序列\(A\)。这个序列长度为\(N\),下标从\(1\)开始。\(A\)的一个子区间对应一个序列,可以由数对\([l,r]\)表示,代表\(A[l],A[l + 1]\) ..., A[r]\(这段数。对于一个序列\)B[1], B[2], ..., B[k]$,定义B的中位数如下:
- 先对B排序。得到新的序列\(C\)。
- 假如\(k\)是奇数,那么中位数为\(C[\frac{k+1}{2}]\)。假如\(k\)为偶数,中位数为\(C[\frac{k}{2}]\)。
对于\(A\)的所有的子区间,小\(N\)可以知道它们对应的中位数。现在小\(N\)想知道,所有长度\(>=Len\)的子区间中,中位数最大可以是多少。
输入描述:
第一行输入两个数\(N\),\(Len\)。
第二行输入序列\(A\),第\(i\)个数代表\(A[i]\)。
输出描述:
一行一个整数,代表所有长度\(>=Len\)的子区间中,最大的中位数。
备注:
数据范围:
30%: n <= 200
60%: n <= 2000
另外有20%:不超过50个不同的数
100%:1<=Len<=n<=10^5, 1 <= a[i] <= 10^9
话说本来写二分,但是被问了,为什么有单调性啊,大的成为中位数小的不一定啊
然后给迷住了
事实上,我们二分答案,得到的不是”答案大于它还是小于它“这样一个东西吗,而不是”它是否可以成为答案“,而且本来就是在求最大值娅
二分以后,把>=的置1,<的置-1
然后我们判断有没有一个长度大于len的区间大于0就可以了
处理前缀和最小值,扫描前缀和就可以了
Code:
#include <cstdio>
#include <algorithm>
const int N=1e5+10;
int a[N],b[N],f[N],n,len;
int min(int x,int y){return x<y?x:y;}
bool check(int p)
{
for(int i=1;i<=n;i++) f[i]=(a[i]>=p?1:-1)+f[i-1];
for(int mi=0,i=len;i<=n;i++)
{
mi=min(mi,f[i-len]);
if(f[i]>mi) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&len);
for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
std::sort(b+1,b+1+n);
int m=std::unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
a[i]=std::lower_bound(b+1,b+1+m,a[i])-b;
int l=1,r=m;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}
printf("%d\n",b[l]);
return 0;
}
2018.9.9
最新文章
- Android基于mAppWidget实现手绘地图(四)--如何附加javadoc
- Android Build Error(1)
- UNIX Time 时间戳 与 北京时间 相互转换
- oracle审计详解-转
- Xamarin.Froms项目中包含的文件
- Neo4j图数据库简介和底层原理
- (转) Lua string 操作函数
- 硬件相关-ADC原理(未完成)
- Linux Kconfig及Makefile学习
- Android设置上下边框或者左右边框
- Jackson基础笔记
- 数据库读写分离Amoeba
- DOM 以及JS中的事件
- ThinkPHP5.0更改框架的验证方法对象->;validate(true)->;save();
- Spark编译及spark开发环境搭建
- PHP幸运大转盘源码,支持ThinkPHP
- 10.18正式开发stark组件*(三)
- DAY5 基本数据类型及内置方法
- Weighted Channel Dropout for Regularization of Deep Convolutional Neural Network
- Delphi 7~XE系列升级安装Indy10.6