题目要求:
给定一个序列和一个 m 的值，要求宰割字符串让其和等于 M，如果有多个依照 i 的程序输入下标 i -j, 如果没有使得宰割的字符串的和等于 M，那么找到最靠近 m 的字符串宰割, 如果有多个依照 i 的从小到大输入下标 i -j
算法思路：
最开始应用了二维数组保留每个终点到各个起点的和，不过内存超限了，因而改用一维数组，咱们能够采纳 partialSum 数组保留终点 1 到 i 的和，
而后任意 i 到 j 地位的间断子序列和为 partialSum[j]-partialSum[i-1]，因为在查找的时候有可能会找的到等于 m 的和也可能找不到，所以咱们先遍历一次，如果能够找的到就让 min_num= M 而后退出循环即可，如果没有就让 min_num 始终更新为最小的大于 m 的值，因为 partialSum 数组是递增的能够采纳二分查找。这里的二分查找应用 STL 库中自带的 upper_bound 函数来实现。
留神点：
1、应用二维数组的形式求解极有可能呈现段谬误和内存超限的状况。提交后果：
AC 代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int N,M;
scanf("%d %d",&N,&M);
int partialSum[N+1];// 保留终点 1 到任意一点的数字和
partialSum[0] = 0;// 终点 0 不存在，然而须要参加计算所以赋值为 0.
for (int i = 1; i <= N; ++i) {scanf("%d",&partialSum[i]);
partialSum[i] += partialSum[i-1];
}
int min_num = 0x3fffffff;// 保留最小的数字，如果存在等于 M 的数字即为 M，如果没有则为大于 M 的最小数
for (int i = 1; i <= N; ++i) {// 取得第一个大于 partialSum[i-1]+ M 的地位 pos,pos- 1 就是最大的小于等于 partialSum[i-1]+ M 的地位
int pos = upper_bound(partialSum+i,partialSum+N+1,partialSum[i-1]+M)-partialSum;
if(partialSum[pos-1]-partialSum[i-1]==M){
// 找到恰好等于 M 的序列和
min_num = M;
break;
}
// 走到这里阐明没有找到等于 M 的序列和
if(pos<=N){// 找到了大于 partialSum[i-1]+ M 才须要保留大于它的最小值，否则会呈现取值出错
min_num = min(partialSum[pos]-partialSum[i-1],min_num);
}
}
// 第二次查找等于 min_sum 的值，肯定能够找到
for(int i=1;i<=N;++i){// 取得第一个大于 partialSum[i-1]+min_num 的地位 pos,pos- 1 就是等于 partialSum[i-1]+min_num 的地位
int pos = upper_bound(partialSum+i,partialSum+N+1,partialSum[i-1]+min_num)-partialSum;
if(partialSum[pos-1]-partialSum[i-1]==min_num){printf("%d-%d\n",i,pos-1);
}
}
return 0;
}