【bzoj1303】[CQOI2009]中位数图
2024-09-30 17:35:24
一个大于b的数和一个小于b的数可以互相抵消,所以我们用1和-1表示。
从b向两边扩展,left[i]表示b左边抵消后有i个数比b小的可能数,right[i]表示b右边抵消后有i个数比b大的可能数。
ans=sigma(left[i]*right[i]).
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std; #define N 200010 int n,b,k; int ans; int a[N];
int l[N],r[N],sum[N]; int main()
{
scanf("%d%d",&n,&b);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]==b)
k=i,a[i]=0;
else
a[i]=a[i]>b ? 1 : -1;
}
l[n]=1;
r[n]=1;
for (int i=k-1;i>=1;i--)
{
sum[i]=sum[i+1]+a[i];
l[sum[i]+n]++;
}
for (int i=k+1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
r[sum[i]+n]++;
}
for (int i=1-n;i<=n-1;i++)
ans+=l[i+n]*r[(n<<1)-(i+n)];
printf("%d",ans);
return 0;
}
最新文章
- WCF学习之旅—TCP双工模式(二十一)
- couchDB文档
- Javascript笔记----实现Page页面右下角置顶按钮.
- 阿里云服务器 FTP配置图文教程和添加两个FTP站点
- java 文件读取大全
- rabbitMQ入门
- MLlib 卡方检验
- 软件体系结构经典问题——KWIC的分析和解决
- JSthis对象
- Android复制iPhone日期和时间选择器
- OpenStack路: OpenStack建筑设计指南 - 概要(摘录和翻译)
- 第18章 备忘录模式(Memento Pattern)
- grep 、find 、tree 新发现
- springboot之fastjson
- vue源码阅读(一)
- Java基础回顾Application(一)
- 将Myeclipse非maven项目,导入到IDEA
- libgdx判断actor与circle是否重叠
- HDU 3480 - Division - [斜率DP]
- FileStream 和StreamWriter 一起用时
热门文章
- A10. JVM 对象
- 在 VS2015+EF6.0中使用Mysql 遇到的坑
- (十二)python3 迭代器
- Python面试快问快答,理论要的就是速度与精准,Python面试题No2
- jmeter 接口测试
- JavaScript - 如果...没有方法(xjl456852修改)
- bash shell &; front-end &; auto publish &; auto deploy
- hdu3592(差分约束) (线性)
- 【bzoj3747】[POI2015]Kinoman - 线段树(经典)
- Django开发:(1)django基础 &; url控制器