ZeroJudge F174: 蛋糕(Cake)

題目敘述

每筆測資第一行有兩個正整數N和K，第二行會有N個整數，分別代表蛋糕的N個區塊。要求輸出如果任意從蛋糕中切取出0~K個區塊，最大的區段和是多少 (如果取任何東西都是負的則可以不要取輸出0)。

範例輸入 #1

7 3 

3 7 -1 9 2 2 1 

範例輸出 #1

15

範例輸入 #2

5 4 

-3 -4 -5 -6 -7 

範例輸出 #2

0

範例輸入 #3

10 4 

1 -5 7 2 5 -2 6 3 0 2 

範例輸出 #3

14

範例輸入 #4

10 5 

10 -3 -5 9 -5 -6 10 7 -20 16

範例輸出 #4

17

範例輸入 #5

10 5 

10 -3 -5 9 -5 -6 10 7 -20 18

範例輸出 #5

18

解題思路

將前綴和存到陣列中之後跑For迴圈判斷每一個數字減掉前K個數字的最小值有沒有比目前最大值 (答案) 還要大，可以使用線段樹來紀錄每一個區段的最小值來防止超時。另外，在進行線段樹搜尋的時候也可以在函式中判斷目前For迴圈中跑到的數字減掉目前節點的值是否有大於答案，如果小於等於的話可以直接return函式節省時間。計算前綴和及計算答案的時候可以使用Long Long Int來防止超過範圍。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
using namespace std;

long long int tree[999999] = {}, ans;
int N, K;
vector<long long int>num;

long long int max(long long int a, long long int b)
{
    if (a > b) return a;
    return b;
}

long long int build(int l, int r, int index)
{
    if (l == r)
    {
        tree[index] = num[l];
        return num[l];
    }
    long long int left = build(l, (l+r)/2, (index*2)+1);
    long long int right = build(((l+r)/2)+1, r, (index*2)+2);
    tree[index] = min(left, right);
    return tree[index];
}

long long int query(int l, int r, int cl, int cr, int index, long long int value)
{
    if (value - tree[index] < ans) return 999999999;
    if (l == cl && r == cr) return tree[index];
    if (cl == cr) return tree[index];
    if (r <= (cl+cr)/2) return query(l, r, cl, (cl+cr)/2, (index*2)+1, value);
    else if (l > (cl+cr)/2) return query(l, r, ((cl+cr)/2)+1, cr, (index*2)+2, value);
    return min(query(l, r, cl, (cl+cr)/2, (index*2)+1, value), query(l, r, ((cl+cr)/2)+1, cr, (index*2)+2, value));
}

long long int math(int l, int r, long long int value)
{
    return query(l, r, 0, N-1, 0, value);
}

long long int calc(long long int hi, int l, int r)
{
    return hi - math(l, r, hi);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    long long int count = 0;
    for (int i = 0; i<N; i++)
    {
        long long int tmp;
        cin >> tmp;
        count += tmp;
        num.push_back(count);
    }
    ans = num[0];
    long long int hi = build(0, N-1, 0);
    for (int i = 1; i<K; i++)
    {
        ans = max(ans, calc(num[i], 0, i-1));
    }
    for (int i = K; i<N; i++)
    {
        ans = max(ans, calc(num[i], i-K, i-1));
    }
    cout << max(ans, 0) << "\n";
}