二分+前缀和+压缩
压缩 二分 前缀
2023-09-27 14:27:32 时间
Powered by:AB_IN 局外人
NEFU-2190 没有名字
大佬AC的,蒟蒻赛后补上,花了好长时间才懂 。
//二分+压缩
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000010],k,ans=0;
int n;
int main()
{
cin>>n>>k;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];//a[i]存的是前i个数的和,这样[L,R]就可以表示为a[r]-a[l-1]
}
for(int i=n;i>=1;i--){
if(a[i]-k>0){//找a[r]-a[l-1]>=k的数,换一下就是a[r]-k>=a[l-1]
//但是1e6的数据,用o(n)会tle,所以用个logn的算法——二分
//固定右端,判断左边,先判断差是否大于0
int cnt=lower_bound(a+1,a+n+1,a[i]-k)-a;//返回第一个比差大于等于的数的下标
ans+=(i-cnt);//则固定右端数 减去 到这个数的所有数都大于k,故i-cnt
}
else
ans+=i;//这个数减k小于0,说明不用再分了,这个数减左边的数(即这个区间的和)都小于k,故为i
}
cout<<ans<<endl;
return 0;
}
借鉴的大佬的想法,本题应该是滑动窗口的题(别人题解这么写的 ),但找一个logn的算法,还是二分香啊~。没有手写二分,因为不用在二分过程中调用,用C++自带的函数即可。
相关文章
- bfs+状态压缩dp
- linux tar压缩解压缩文件夹、文件命令详解
- JDK9的新特性:String压缩和字符编码
- 【BZOJ5299】【CQOI2018】解锁屏幕(动态规划,状态压缩)
- 压缩、系列化对象
- ios mac 对照片进行JPEG压缩
- Linux Command tar 压缩
- 两个案例:展现高效的压缩的重要性
- HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)
- Android ProGuard:代码混淆压缩
- android图片压缩的3种方法实例
- 压缩字符流和字节流和全站压缩过滤器
- java实现图片压缩与拼接
- 【bzoj3312】[Usaco2013 Nov]No Change 状态压缩dp+二分