这道题可以利用二分来做,其实个人觉得动态规划也可以;利用二分的前提条件就是该序列是一个不下降序列;所以我们可以先构建一个 sum 数组,存放 1 - i 的和值;当然题目中要计算 i - j 子序列的值,其实这个可以利用 sum 数组来计算,该子序列的和就是 sum[j]-sum[i];所以我们就相当于对 sum 和二分序列寻找 sum[i]+x,其中,x 为题目前提给出的和值;
对于二分算法,使用大于 x 和大于等于 x 的两种都可以,示例给出的是大于 x,然后通过判断 j - 1 位是不是可以使得子序列和等于 x; 个人觉得麻烦,还是使用大于等于 x 较为简单;
其实这道题的关键还是怎么转化数组使得其能够用二分法进行解决;还有一个问题,如果不仅仅包括 0 - n 位,会出现第 n 位元素无法进行判断的情况,所以包括的序列一定要为 1~n+1,这样就可以有效的使得随后一位进行计算,使得小于 x 的时候出现第 n + 1 位无效位,从而根据位数是否无效来剔除这种意外之外的情况;
算法实现如下,使用的是大于等于 x:
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
const int maxn=100010;
int a[maxn],sum[maxn];
int n,m,ns=100000010;
int binarySearch(int l,int r,int x){
while(l<r){
int mid=(l+r)/2;
if(sum[mid]>=x){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
int main(){
scanf(“%d”,&n);
scanf(“%d”,&m);
for(int i=1;i<=n;i++){
scanf(“%d”,&a[i]);
}
sum[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
// 此时 sum 递增;
for(int i=1;i<=n;i++){
int j=binarySearch(i,n+1,sum[i-1]+m);
if(sum[j]-sum[i-1]==m){
// 如果存在和 s 相等的数;
ns=m;
break;
}else if(j<=n&&sum[j]-sum[i-1]<ns){
ns=sum[j]-sum[i-1];
}
}
for(int i=1;i<=n;i++){
int j=binarySearch(i,n+1,sum[i-1]+ns);
if(sum[j]-sum[i-1]==ns){
printf(“%d-%d\n”,i,j);
}
}
system(“pause”);
return 0;
}