1044. Shopping in Mars (25)

分析：

　　考察二分，简单模拟会超时，优化后时间正好，但二分速度快些，注意以下几点：

　　　　(1)：如果一个序列D ... D如果我们计算D到D的和， 那么我们可以计算D到D的和sum1，D到D的和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 = ;

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 = , high = n;

    while (low <= high)

    {

        int mid = (low + high) >> ;

        if (sum[mid] == target)

            return mid;

        else if (sum[mid] < target)

            low = mid + ;

        else high = mid - ;

    }

    return low;

}

int main()

{

    int n, m;

    while (scanf("%d%d", &n, &m) != EOF)

    {

        for (int i = ; i <= n; i++)

        {

            scanf("%d", &value[i]);

            sum[i] = sum[i - ] + value[i];

        }

        int Min = Max_Int;

        for (int i = ; 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 >=  && 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 + ;

                    node.end = res;

                    V_node.push_back(node);

                }

                else if (sum[res] - sum[i] - m == Min)

                {

                    Node node;

                    node.start = i + ;

                    node.end = res;

                    V_node.push_back(node);

                }

            }

        }

        for (int i = ; i < V_node.size(); i++)

            printf("%d-%d\n", V_node[i].start, V_node[i].end);

    }

    return ;

}