当前位置: 首页 > news >正文

动态网站登录加注册怎么做郑州官网网络营销外包

动态网站登录加注册怎么做,郑州官网网络营销外包,网站策划方案论文,建议网站的方案123 二分等差数列求和前缀和数组 题目分析 连续一段的和我们想到了前缀和,但是这里的l和r的范围为1e12,明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点,可以按照等差数列对序列进行分块。如上图,在求前10个…

123

二分+等差数列求和+前缀和数组

题目分析

连续一段的和我们想到了前缀和,但是这里的l和r的范围为1e12,明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点,可以按照等差数列对序列进行分块。如上图,在求前10个数的和的时候,我们可以这样求1+3(1+2)+6(1+2+3)+10(1+2+3+4)=20。我们不需要遍历10次就可以求出来。求前缀和代码如下

sum = new long[1500010];
for (int i = 1; i <= 1500000; i++) {t += i;sum[i] = sum[i-1]+t;
}

这里的t最开始等于1,是第一块的数字和,然后等于3,是第二块数字的和,然后等于6是第三块数字的和,以此类推。sum[i]表示的是分块后前i块包含数字的和。

我们可以求出前n块数字的和,那么我们需要知道第l个数字是在哪一块里面,然后求第l个数字是所在块的第几个数字。因为对于最后一块来说,不是所有的数字都会被包含进来,我们要单独对最后一块求数字和。

第一阶段利用二分求第x个数所在的块

​ 图1

如图1所示,我们可以把这个序列分块,第一块有1个数,第二块有2个数,第三块有3个数,第四块有4个数,每一块拥有数的个数是一个等差数列。现在要找到序列中第x个数所在的块数,假设x=3,那么第x个数在第2块中,如果x=4,那么第x个数在第3块中。求第x个数所在的块数,就是求从左往右数,前缀和第一个大于等于x的块。

比如第2块的前缀和就是3,第三块的前缀和就是5。这个可以用二分去求。

    int l = 1;int r = 1500000;//最多可以分的块数while(l < r) {int mid = (l + r) / 2;if(sum(mid) < x) {//求mid个块中包含的数字的个数,如果小于x,就是不符合条件,我要向左找l = mid + 1;}else {//符合条件,我要看前面的块是否也是大于等于x的r = mid;}}

这里的sum函数的作用就是求前mid块中包含的数字的个数,因为是等差数列,所以直接用等差数列的求和公式就可以了,sum函数如下

private static long sum(long x) {    return (1L + x) * x / 2;
}

第二阶段求前x个数的前缀和

接下来分析二分结束之和我要怎么操作,我要求前x个数字的和。

假设x=8,那么第x个数在第4块中,我还要知道,第x个数是第4块中的第几个数字。如图,第4块有4个数,第x个数第4块的第2个数上,那么第2个数是怎么来的呢?就是x-sum(r-1)=8-6=2。其实就是我二分算出来了第x个数在第r块上,那么我只需要把前r-1块包含的数的个数减去就算出来x是在第r块上的第几个数上了。结合上图更好理解。那么前x个数的和就是前r-1块包含数的和加上第r块里面前x-sum(r-1)个数的和。

某一块里面包含的数也是等差数列,求前n个数的和依然可以直接用sum(n)去求。而数组sum[r]里面记录的是前r块包含数字值的前缀和。所以二分结束后的代码是这样子的

private static long f(long x) {int l = 1;int r = 1500000;//最多可以分的块数while(l < r) {int mid = (l + r) / 2;if(sum(mid) < x) {//求mid个块中包含的数字的个数l = mid + 1;}else {r = mid;}}//r--是表示完整的块的个数r--;//就是上文里的r-1//x表示x处在他所在块的第几个位置,需要减去前面所有块包含的数的个数//本来要求x个数字,前r个块中已经包含了sum(r)个数字,第r+1个块x -= sum(r);//前r个块中已经包含了多少个数字return sum[r]+sum(x);
}

还是对于x=8的例子,二分求出来r=4,r–后,r=3,sum[3]=10。x-=sum(3)=8-6=2。sum[3]+sum(2)=10+3=13

注意这道题里对于sum函数的多次应用,但是不是每一次应用含义都是一样的。因为每一块包含的数字个数是等差数列,而每一块内每个数字形成的也是等差数列。

题目代码

import java.util.Scanner;
public class Main {
static long[] sum;
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long t = 0;//前缀和的预处理sum = new long[1500010];for (int i = 1; i <= 1500000; i++) {t += i;sum[i] = sum[i-1]+t;}int n = scanner.nextInt();while(n-- > 0) {long l = scanner.nextLong();long r = scanner.nextLong();System.out.println(f(r)-f(l-1));//f(r)求的是序列中前r个数的和}
}
//二分  二分求的是x在哪一块中 n*(n-1)/2>l的第一个n
private static long f(long x) {int l = 1;int r = 1500000;//最多可以分的块数while(l < r) {int mid = (l + r) / 2;if(sum(mid) < x) {//求mid个块中包含的数字的个数l = mid + 1;}else {r = mid;}}//r--是表示完整的块的个数r--;//x表示x处在他所在块的第几个位置,需要减去前面所有块包含的数的个数//本来要求x个数字,前r个块中已经包含了sum(r)个数字,第r+1个块x -= sum(r);//前r个块中已经包含了多少个数字return sum[r]+sum(x);
}
//sum函数求前x块包含的数的个数,同时也可以表示某一个块中,前x个数的总和
private static long sum(long x) {// TODO Auto-generated method stub    return (1L + x) * x / 2;
}
}
http://www.dt0577.cn/news/20808.html

相关文章:

  • 视频网站怎么做压力测试海淀区seo搜索引擎
  • 网站建设基础ppt互联网广告营销方案
  • 独立商城系统网站建设国际新闻最新消息10条
  • wordpress 文章在数据库seo包年优化平台
  • 内涵吧网站免费搭建网站
  • 哪个网站有上门做指甲鼓楼网页seo搜索引擎优化
  • 旅游网站做精准营销的百度服务中心人工24小时电话
  • 万网个人网站建设教程广州seo黑帽培训
  • 个人网站怎么做推广网络广告宣传怎么做
  • 佳木斯网站设计全国防疫大数据平台
  • 公司交易平台网手机端seo
  • wordpress企业网站制作产品营销推广
  • 建站快车是什么国内最好的seo培训
  • 电商网站设计文档手机网页设计
  • 企业电商网站备案流程网站按天扣费优化推广
  • 2022网页游戏排行榜seo综合查询国产
  • 域名有关的网站seo排名赚能赚钱吗
  • 甘肃住房建设厅的网站西安做网站的网络公司
  • 手机创建网站的软件吉林网络推广公司
  • 江门靠谱网站建设优化cpu优化软件
  • 高端网站设计哪里比较好徐州百度推广公司
  • 网站备案资料下载百度网盘电话人工服务
  • 门户网站制作的公司广告语
  • 品牌建设经费投入占销售比重湖南优化推广
  • 哪里做网站靠谱优化防疫措施
  • 可以做qq空间背景音乐的网站seo零基础培训
  • 本地网站环境搭建app开发费用标准
  • 网站运营seo招聘宁波百度推广优化
  • 网站页面设计版权seo博客网站
  • 南通购物网站建设百度搜索引擎