福州大学算法作业题 - 加法运算

2018-10-29 15:26:24来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

★实验任务 

小学一年级的期末考试上,老师出了这样一道题:给出一排数字,选择其中 位置连续的若干个数字,计算它们的和,要求这些数字的和满足大于等于 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选择客栈