分析：
考察二分，简单模拟会超时，优化后时间正好，但二分速度快些，注意以下几点：
（1）：如果一个序列D1 … Dn,如果我们计算Di到Dj的和， 那么我们可以计算D1到Dj的和sum1,D1到Di的和sum2, 然后结果就是sum1 - sum2;
（2）： 那么我们二分则要搜索的就是m + sum[i]的值。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cctype>
#include <iomanip>
#include <cmath>
#include <map>
using namespace std;
const int Max_Int = 0x7fffffff;
const int Max_required = 100005;
int sum[Max_required];
int value[Max_required];
struct Node
{
int start;
int end;
};
vector<Node> V_node;
int binary_find（int target, int n）
{
int low = 0, high = n;
while （low <= high）
{
int mid = （low + high） 》 1;
if （sum[mid] == target）
return mid;
else if （sum[mid] < target）
low = mid + 1;
else high = mid - 1;
}
return low;
}
int main（）
{
int n, m;
while （scanf（"%d%d", &n, &m） != EOF）
{
for （int i = 1; i <= n; i++）
{
scanf（"%d", &value[i]）；
sum[i] = sum[i - 1] + value[i];
}
int Min = Max_Int;
for （int i = 0; i <= n; i++）
{
int target = m + sum[i];
int res = binary_find（target, n）；
//printf（"res = %d\n", res）；
if （sum[res] - sum[i] - m >= 0 && sum[res] - sum[i] - m <= Min）
{
if （sum[res] - sum[i] - m < Min）
{
V_node.clear（）；
Min = sum[res] - sum[i] - m;
Node node;
node.start = i + 1;
node.end = res;
V_node.push_back（node）；
}
else if （sum[res] - sum[i] - m == Min）
{
Node node;
node.start = i + 1;
node.end = res;
V_node.push_back（node）；
}
}
}
for （int i = 0; i < V_node.size（）； i++）
printf（"%d-%d\n", V_node[i].start, V_node[i].end）；
}
return 0;
}
View Code |