2020-2021 ACM-ICPC, Asia Seoul Regional Contest L Two Buildings

题目描述

http://codeforces.com/gym/102920/problem/L

简要题意：给定一个长度为 $n$ 的序列 $h_i$，求最大的数对 $(i,j),i<j$，其中 $(h_i+h_j)\times (j-i)$ 最大

$n\le 10^6$

Solution

显然对于 $h_i$ 我们只会选择前缀最大值，对于 $h_j$ 我们只会选择后缀最大值，我们考虑对于每个 $h_j$ 求最大的 $h_i$，同时我们猜测这东西有决策单调性，所以我们用分治的做法即可解决问题

时间复杂度 $O(n\log n)$

不过为了严谨我们还是来证明一下

不妨设 $i$ 的决策点为 $j$，那么 $\forall k<j,(a_i+a_j)(i-j)\ge (a_i+a_k)(i-k)$

我们考虑 $i+1$ 的决策点，如果满足决策单调性，那么一定有 $\forall k<j,(a_{i+1}+a_j)(i-j)\ge (a_{i+1}+a_k)(i-k)$

我们考虑这个式子相当于 $i$ 的式子有什么改变

能够得到不等式两边的增量为 $(a_{i+1}-a_i)(i-j)+a_{i+1}$ 和 $(a_{i+1}-a_i)(i-k)+a_{i+1}$

由于 $a_{i+1}<a_i$，所以右边的增量小，所以该不等式依然满足

#include <iostream>
#include <algorithm>
#define maxn 1000010
#define ll long long
using namespace std;

int n, h[maxn];

ll w(int i, int j) { return 1ll * (h[i] + h[j]) * (j - i); } 

int a[maxn], b[maxn]; ll ans;
void solve(int l, int r, int L, int R) {
    if (l > r) return ; int m = l + r >> 1, p = L; ll res = 0; 
    for (int i = L; i <= R && a[i] < b[m]; ++i)
        if (w(a[i], b[m]) > res) res = w(a[i], b[m]), p = i;
    ans = max(ans, res); 
    solve(l, m - 1, L, p); solve(m + 1, r, p, R); 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; int c1 = 0, c2 = 0; 
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) 
        if (!c1 || h[i] > h[a[c1]]) a[++c1] = i;
    for (int i = n; i; --i)
        if (!c2 || h[i] > h[b[c2]]) b[++c2] = i;
    reverse(b + 1, b + c2 + 1); solve(1, c2, 1, c1);
    cout << ans << "\n"; 
    return 0;
}