Two Buildings（决策单调性+分治）

题目大意：
给定一个长度为 $n$ 的数组 $h$ 求：
m a x ( ( h i + h j ) ( j − i ) ) max(\ (h_i+h_j)(j-i)\ ) max( (hi​+hj​)(j−i) )
题目分析：
此题可转化为求：
m a x ( ( h j − ( − h i ) ) ( j − i ) ) max(\ (h_j-(-h_i))(j-i)\ ) max( (hj​−(−hi​))(j−i) )
这个就相当于在二维坐标系中求最大矩形的面积，我们设 $a,b$ 数组分别为矩形的左下角和右上角那两个坐标的纵坐标（其横坐标就是其数组下标），则题目所求即为：
m a x ( ( b j − a i ) ( j − i ) ) max(\ (b_j-a_i)(j-i)\ ) max( (bj​−ai​)(j−i) )
将上式和题目所求联立可得 a i = − h i , b i = h i a_i=-h_i,b_i=h_i ai​=−hi​,bi​=hi​ ，这样我们就可以得到 $a,b$ 数组了
我们继续考虑如何求 m a x ( ( b j − a i ) ( j − i ) ) max(\ (b_j-a_i)(j-i)\ ) max( (bj​−ai​)(j−i) )：
我们发现对于一个给定 a i a_i ai​ 在选择 b j b_j bj​ 与之配对时 b j b_j bj​ 是有决策单调性的：越往右上越优，即对于下面两个决策：
b i ≤ b j ( i < j ) b_i\le b_j(ibi​≤bj​(i<j)
决策 b j b_j bj​ 显然优于决策 b i b_i bi​ 所以可以直接将 b i b_i bi​ 状态删掉，对 $a$ 数组同理（如果不理解在纸上画一画图可能就明白了）
接下来我们考虑如何快速处理出答案：
设 $a,b$ 数组分别有 $n,m$ 个元素（已按从左下到右上排好序）， $a.x$ 表示原数组下标即二维平面的横坐标， $a.y$ 表示二维平面的那个纵坐标， $b$ 数组同理
用 $solve(l1,r1,l2,r2)$ 表示 $a$ 数组下标从 $l1$ 到 $r1$ ， $b$ 数组从 $l2$ 到 $r2$ 的最优解，我们采用一下过程进行分治：
取 m i d = l 1 + r 1 2 mid=\frac{l1+r1}2 mid=2l1+r1​ 我们扫描 $b$ 数组并记录对 a m i d a_{mid} amid​ 的最优解的下标 $pos$ ，然后答案就是 a m i d , b p o s a_{mid},b_{pos} amid​,bpos​ 构成的矩形， $solve(l1,mid-1,l2,pos)$ ， $sovle(mid+1,r1,pos,r2)$ 三者的最大值（因为决策是具有单调性的）

具体细节见代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
ll read()
{ll res = 0,flag = 1;char ch = getchar();while(ch<'0' || ch>'9'){if(ch == '-') flag = -1;ch = getchar();}while(ch>='0' && ch<='9'){res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';ch = getchar();}return res*flag;
}
const int maxn = 5e6+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct node{ll x,y;bool operator < (const node b) const {if(x == b.x) return y < b.y;return x < b.x;}
}a[maxn],b[maxn];
ll n,m,h[maxn];
bool vis[maxn];
void init_a()
{memset(vis,0,sizeof(vis));sort(a+1,a+n+1);int last = 1,cnt = 0;for(int i = 2;i <= n;i++)if(a[i].y >= a[last].y) vis[i] = true;else last = i;for(int i = 1;i <= n;i++)if(!vis[i]) a[++cnt] = a[i];n = cnt;
}
void init_b()
{memset(vis,0,sizeof(vis));sort(b+1,b+m+1);int last = m,cnt = 0;for(int i = m-1;i;i--)if(b[i].y <= b[last].y) vis[i] = true;else last = i;for(int i = 1;i <= m;i++)if(!vis[i]) b[++cnt] = b[i];m = cnt;
}
ll calc(ll i,ll j)
{if(a[i].x>b[j].x && a[i].y > b[j].y)return -Inf;return (b[j].x-a[i].x)*(b[j].y-a[i].y);
}
ll solve(ll l1,ll r1,ll l2,ll r2)
{if(l1>r1 || l2>r2) return 0;int mid = l1+r1>>1;int pos = l2;for(int i = l2+1;i <= r2;i++)if(calc(mid,pos) < calc(mid,i))pos = i;return max({calc(mid,pos),solve(l1,mid-1,l2,pos),solve(mid+1,r1,pos,r2)});
}
int main()
{n = read();m = n;for(int i = 1;i <= n;i++){h[i] = read();a[i].x = b[i].x = i;a[i].y = -h[i];b[i].y = h[i];}init_a();init_b();printf("%lld\n",solve(1,n,1,m));return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！