2013-02-22 20:52:30Morris
[ZJ][heap] a605. 交錯和
內容 ：
給定一個整數數列 <an>，考慮下標數列 <bm>，其中 m≠0 且 1≦b1＜b2＜...＜bm≦n，我們定義交錯和 σb = ab1-ab2+ab3-ab4+...。
已知 bi+1-bi≦δ，試求 σb 的最大值。
輸入說明 ：
測試資料第一行有兩個整數 n(n≦1000000) 與 δ(1≦δ≦n-1)。
接下來有 n 個整數，其中第 i 個整數為 ai。
輸出說明 ：
輸出 σb 的最大值。
範例輸入 ：
5 11 4 3 2 5----我是分隔線----5 21 4 3 2 5
範例輸出 ：
6----我也是分隔線----7
提示 ：
出處 ：
原創問題，如有雷同，純屬巧合 (管理：xavier13540)
使用兩個 heap 去維護，一個是前一次是用 +, 另一是前一次是用 -
然後要記錄 index 的位置，然後可能會是一個沒用的，即可拋棄。
※ 可能會有負數。
使用兩個 heap 去維護，一個是前一次是用 +, 另一是前一次是用 -
然後要記錄 index 的位置，然後可能會是一個沒用的，即可拋棄。
※ 可能會有負數。
/**********************************************************************************/
/* Problem: a605 "交錯和" from 原創問題，如有雷同，純屬巧合 */
/* Language: CPP (1755 Bytes) */
/* Result: AC(152ms, 2.7MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-02-22 20:56:34 */
/**********************************************************************************/
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
struct E {
long long v;
int i;
};
struct cmp {
bool operator() (E a, E b) {
return a.v < b.v;
}
};
int main() {
int i, n, m;
while(scanf("%d %d", &n, &m) == 2) {
priority_queue<E, vector<E>, cmp> Q1, Q2; // plus, minus
long long ans = -(1LL<<60), Ai;
E a, b, c, d;
for(i = 0; i < n; i++) {
scanf("%lld", &Ai);
if(Ai > ans) ans = Ai;
c.i = d.i = -1;
while(!Q1.empty()) {
a = Q1.top();
if(a.i < i-m) {
Q1.pop();
continue;
}
b.v = a.v - Ai, b.i = i;
if(b.v > ans) ans = b.v;
c = b;
break;
}
while(!Q2.empty()) {
a = Q2.top();
if(a.i < i-m) {
Q2.pop();
continue;
}
b.v = a.v + Ai, b.i = i;
if(b.v > ans) ans = b.v;
d = b;
break;
}
a.v = Ai, a.i = i;
if(c.i != -1) {
while(!Q2.empty() && c.v > Q2.top().v)
Q2.pop();
Q2.push(c);
}
if(d.i != -1) {
while(!Q1.empty() && (d.v > Q1.top().v || a.v > Q1.top().v))
Q1.pop();
if(d.v > a.v)
Q1.push(d);
else
Q1.push(a);
} else Q1.push(a);
}
printf("%lld\n", ans);
}
return 0;
}