★实验任务
小学一年级的期末考试上,老师出了这样一道题:给出一排数字,选择其中 位置连续的若干个数字,计算它们的和,要求这些数字的和满足大于等于 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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606606.html