21.1.27 2020-2021 ACM-ICPC, Asia Seoul Regional Contest
A是模拟，扔给神仙队友就完事了
没听讲题，I不会啊/kk
G. Mobile Robot √
(Description)
给定(n)个机器人及其位置(p_i)，和一个数(d)，你需要给每个机器人找一个新位置(p'_i)使得机器人从(1)到(n)所在位置为公差为(d)的等差数列，求最小的(max_{i=1}^n|p_i-p'_i|)。
(nleq10^6)。
(Solution)
其实比较有意思。只要第一个位置(x)确定，其它位置即(xpm(i-1)d)，所以就是使(max|p_i-xpm(i-1)d|=max|(p_ipm(i-1)d)-x|=max|A_i-x|)最小。(x)任取，显然(max A_i-min A_i)除以(2)即为答案。
注意整数即使只是除以(2)，保留一位小数也会有精度误差。。（不是(X.5)）所以要手动输出(X.5)。
还有常数(5)是个int型变量输出要用%d。。（运算没问题，编译器旧点输出会有点问题）
//514ms 15700KB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
typedef long long LL;
const int N=1e6+5;
const LL INF=1e17;
LL p[N];
inline LL read()
{
LL now=0,f=1; char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now*f;
}
int main()
{
int n=read(); LL d=read(),A;
for(int i=1; i<=n; ++i) p[i]=read();
LL mn=INF,mx=-INF;
for(int i=1; i<=n; ++i) A=p[i]-(i-1)*d, mn=std::min(mn,A), mx=std::max(mx,A);
LL ans=mx-mn;
mn=INF,mx=-INF;
for(int i=1; i<=n; ++i) A=p[i]+(i-1)*d, mn=std::min(mn,A), mx=std::max(mx,A);
ans=std::min(ans,mx-mn);
printf("%lld.%lld
",ans/2,ans%2?5ll:0ll);//%.1f不行！ 常数输出时要保证是longlong。。
return 0;
}
L. Two Buildings(分治 决策单调性)
(Description)
给定一个序列(h_i)，求(max_{1leq i<jleq n}(h_i+h_j)*(j-i))。
(nleq10^6)。
(Solution)
这种区间题考虑分治，如何求过(mid)的区间的答案。
可以发现对左边区间只有递增的(h_i)是有用的，同理右边区间只需要考虑递减的(h_i)。
找出单调的这些(h_i)记为(A_i)，然后考虑对左区间的每个(A_i)找到右边最优匹配的那个位置(p_i)，那么(p_i)是单调增加的。（可以想象二维平面上两点构成的矩形面积，或者感性理解一下）
也就是满足决策单调性。分治换一种写法，先弄出整个序列的单调的(h_i)。然后直接暴力求出当前区间(mid)的最优匹配点(p)，然后对([l,mid-1])、([mid+1,r])区间再递归，其需考虑的决策范围为([L,p])和([p,R])。
每次复杂度(O(决策范围))，即每层(O(n))，每层会删(1,2,4,...)个元素所以是(O(log))层，复杂度(O(nlog n))。
//342ms 11700KB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
typedef long long LL;
const int N=1e6+5;
int A1[N],A2[N],h[N];
LL Ans;
inline int read()
{
int now=0,f=1; char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now*f;
}
#define Calc(p) (1ll*(h[A1[mid]]+h[A2[p]])*(A2[p]-A1[mid]))
void Solve(int l1,int r1,int l2,int r2)
{
if(l1>r1) return;
int mid=l1+r1>>1,pos=l2;
for(int i=l2+1; i<=r2; ++i)
if(Calc(i)>Calc(pos)) pos=i;
Ans=std::max(Ans,Calc(pos));
Solve(l1,mid-1,pos,r2), Solve(mid+1,r1,l2,pos);
}
int main()
{
int n=read();
for(int i=1; i<=n; ++i) h[i]=read();
int cnt1=1,cnt2=1; A1[1]=1, A2[1]=n;
for(int i=2; i<=n; ++i)
if(h[i]>h[A1[cnt1]]) A1[++cnt1]=i;
for(int i=n-1; i; --i)
if(h[i]>h[A2[cnt2]]) A2[++cnt2]=i;
Solve(1,cnt1,1,cnt2), printf("%lld
",Ans);
return 0;
}