题目要求:
给定一个序列和一个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;}