福州大学算法作业题 - 加法运算
2018-10-29 15:26:24来源:博客园 阅读 ()
★实验任务
小学一年级的期末考试上,老师出了这样一道题:给出一排数字,选择其中 位置连续的若干个数字,计算它们的和,要求这些数字的和满足大于等于 a,小 于等于 b 的条件。快速统计出子序列数量的同学,可以得到满分!
小明回家之后,请教了他正在读研究生的表哥 mcginn,mcginn 大手一挥, 写下了一段代码,快速高效地解决了这个问题,从此小明立志成为一名码农!
★数据输入
输入一个 n 表示数字个数,以及 a 和 b(|a|,|b| <= 100000) 输入一个数组 nums[],(|nums[i]| <= 100000)表示数字
★数据输出
输出一个数字表示满足条件的连续子序列有几种
注意:统计结果不包括空序列
★数据范围
80%的得分点,n<=1000 其余 20%的得分点,n<=100000
代码1:
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <stdlib.h> #include <vector> #include <queue> using namespace std; class Search { public: int mergeSort(vector<long>& sum, int left, int right, int lo, int hi) { if(hi-lo <= 1) return 0; int mid = (lo+hi)/2, m = mid, n = mid, count =0; count = mergeSort(sum,left,right,lo,mid) + mergeSort(sum,left,right,mid,hi); for(int i =lo; i< mid; i++) { while(m < hi && sum[m] - sum[i] < left) m++; while(n < hi && sum[n] - sum[i] <= right) n++; count += n - m; } inplace_merge(sum.begin()+lo, sum.begin()+mid, sum.begin()+hi); return count; } int countRangeSum(vector<int>& nums, int left, int right) { int len = nums.size(); vector<long> sum(len + 1, 0); for(int i =0; i< len; i++) sum[i+1] = sum[i]+nums[i]; return mergeSort(sum, left, right, 0, len+1); } }s; int main(){ int n,a,b,i; scanf("%d %d %d",&n,&a,&b); vector<int> nums(n,0); for(i=0;i<n;i++){ scanf("%d",&nums[i]); } int count=s.countRangeSum(nums,a,b); printf("%d",count); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:福州大学算法作业题 - 数列
下一篇:LG-P1311选择客栈
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash