hihoweek 16求指教

0
0

求指教,程序TLE了。

 #include <iostream>
    #define INT_MAX 2147483647
    using namespace std;
    int FillSegmentationTree(int left, int right);
    int FindSegmentationTree(int lowerBound, int rightBound, int left, int right);
    int FindNormal(int left, int right);

    int* weight;
    int* segmentationTreeMin;

    int main(char* argv[], int argc)
    {
        int N;
        cin >> N;
        weight = new int[N + 1];
        for (int i = 0; i < N; i++)
        {
            cin >> weight[i + 1];
        }
        segmentationTreeMin = new int[N + 1];
        for (int i = 0; i <= N; i++)
        {
            segmentationTreeMin[i] = INT_MAX;
        }

        FillSegmentationTree(1, N);

        int Q;
        cin >> Q;
        int L, R;
        for (int i = 0; i < Q; i++)
        {
            cin >> L >> R;
            cout << FindSegmentationTree(1, N, L, R) << endl;
        }
    }

    int FindNormal(int left, int right)
    {
        int min = INT_MAX;
        for (int i = left; i <= right; i++)
        {
            if (weight[i] < min)
            {
                min = weight[i];
            }
        }
        return min;
    }

    int FillSegmentationTree(int left, int right)
    {
        if (left == right)
        {
            return weight[left];
        }
        else if (right - left == 1)
        {
            int mid = (left + right) / 2;
            segmentationTreeMin[mid] = weight[left] < weight[right] ? weight[left] : weight[right];
            return segmentationTreeMin[mid];
        }
        else
        {
            int mid = (left + right) / 2;
            int leftMin = FillSegmentationTree(left, mid);
            int rightMin = FillSegmentationTree(mid + 1, right);
            segmentationTreeMin[mid] = leftMin < rightMin ? leftMin : rightMin;
            return segmentationTreeMin[mid];
        }
    }

    int FindSegmentationTree(int lowerBound, int rightBound, int left, int right)
    {
        if (rightBound == lowerBound)
        {
            return weight[lowerBound];
        }
        else 
        {
            int mid = (lowerBound + rightBound) / 2;
            if (left == lowerBound && right == rightBound)
            {
                return segmentationTreeMin[mid];
            }
            else if (right <= mid)
            {
                return FindSegmentationTree(lowerBound, mid, left, right);
            }
            else if (left > mid)
            {
                return FindSegmentationTree(mid + 1, rightBound, left, right);
            }
            else
            {
                int leftMin = FindSegmentationTree(lowerBound, mid, left, mid);
                int rightMin = FindSegmentationTree(mid + 1, rightBound, mid + 1, right);
                return leftMin < rightMin ? leftMin : rightMin;
            }
        }
    }
  • segment tree虽然通用但容易由于写不好而使得常数耗费大。你先用提示1里面的sparse table的方法试试,代码短小精悍

  • 添加评论
  • reply

0 answer(s)

write answer 切换为英文 切换为中文


转发分享