计蒜客入门赛#2 数列 一次前缀和+二分区间（lower_bound）

网友投稿 726 2022-11-06

计蒜客入门赛#2 数列 一次前缀和+二分区间（lower_bound）

计蒜客入门赛#2 数列 一次前缀和+二分区间（lower_bound）

​​传送门​​​ 题意：好理解 思路：后面数太大，不能用暴力。考虑数比较大，但又是连续的区间，使用前缀和构建一个新的序列。 再二分这个序列的区间，寻找正好大于等于目标（lower_bound）的数。 ps；被cin/cout坑死，输入输出量太大 还是scanf/printf稳

#include#include#include#include#include#include#include#include#include#include#include#include#define ll long long#define N 100010using namespace std;const ll maxn = 1000000 + 5;const ll mod= 1e9+7;//ll b[maxn];//ll vis[maxn], Bool[maxn];//ll a[maxn];ll ai[maxn],a[maxn],num[maxn],sum[maxn];using namespace std;//vectora;ll bsearch5(ll low,ll high,ll k){//直接套模板 k==key ll mid; while(low < high){ mid = low + (high -low)/2;//mid==被分的区间 if(sum[mid] >= k){ high = mid; } else{ low = mid + 1; } } return num[high];}int main() { ios::sync_with_stdio(false); ll n,q; scanf("%lld %lld",&n,&q);//数字的个数//数字 ll ty=n; ll cnt=0; while(n--) { cnt++; //cin>>ai[cnt]>>num[cnt]; scanf("%lld %lld",&ai[cnt],&num[cnt]); //sum+=ai[cnt]; //cnt++; } cnt=0; ll t=0; ll k; for(ll i=1;i<=ty;i++) { sum[i]=ai[i]+t; t=sum[i]; } for(ll i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：序列
上一篇:计蒜客 颜色 dfs + set
下一篇:计蒜客 补码 模拟题
相关文章

 发表评论

暂时没有评论，来抢沙发吧~