ZeroJudge F174: 蛋糕(Cake)

小明過生日，家人為他準備一個長方型的水果蛋糕，由於他是壽星，他可以先切蛋糕去吃。這個蛋糕分成 N 小塊，每塊都有一種餡料。
小明對每種餡料有不同的喜好度，喜好度數值若為正值代表喜歡，負值代表厭惡，零值為沒有感覺。 為了省時間，小明只挑連續一段蛋糕來吃，
這樣就只要切一刀或兩刀。而且，為了讓其它人也能吃到蛋糕，他「至多」只會挑 K小塊的份量吃，（可以不拿滿 K小塊分量的蛋糕，甚至是不拿）。
舉例而言：假如 N = 7、K = 3，每小塊蛋糕小明 給的喜好度評分如下： 3 7 -1 9 2 2 1
拿到 [7, -1, 9] 這三塊蛋糕的總分最高，為 15 分，縱使中間的他不喜歡吃 也沒關係。雖然 [9, 2, 2] 這段蛋糕他全部都喜歡，不過總分只有 13 分。
請你寫一個程式計算出小明能吃到的蛋糕最高總分為多少分。

範例測資

範例輸入範例輸出
第一行有兩個正整數 N (1 <= N <= 105) 和 K (1 <= K <= N)，
分別表示長方形蛋糕有 N 小塊，小明至多可以拿走相當於 K 小塊的連續區段蛋糕。
接下來一行有 N 個整數，依序代表由左至右每一小塊蛋糕的評分
Si (|Si| <= 100)，兩個整數以一個 空白隔開。		請輸出一行整數，表示小明能吃到的蛋糕的最高分，如果完全不拿，輸出 0。
7 3
3 7 -1 9 2 2 1		15
5 4
-3 -4 -5 -6 -7		0
10 4
1 -5 7 2 5 -2 6 3 0 2		14
10 5
10 -3 -5 9 -5 -6 10 7 -20 16		17
10 5
10 -3 -5 9 -5 -6 10 7 -20 18		18
ZeroJudge F174 範例測資

解題思路

將前綴和存到陣列中之後跑 For迴圈 判斷每一個數字減掉前 K 個數字的最小值有沒有比目前最大值 (答案) 還要大，可以使用線段樹來紀錄每一個區段的最小值來防止超時。

另外，在進行線段樹搜尋的時候也可以在函式中判斷目前 For迴圈 中跑到的數字減掉目前節點的值是否有大於答案，如果小於等於的話可以直接 return 函式節省時間。計算前綴和及計算答案的時候可以使用 Long Long Int 來防止超過範圍。

範例程式碼－ZeroJudge F174: 蛋糕(Cake)

#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";
}

//ZeroJudge F174
//Dr. SeanXD
標籤

相關文章

發佈留言