小明過生日,家人為他準備一個長方型的水果蛋糕,由於他是壽星,他可以先切蛋糕去吃。這個蛋糕分成 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 |
解題思路
將前綴和存到陣列中之後跑 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