题解：P10989 [蓝桥杯 2023 国 Python A] 等腰三角形
北文
·
2024-08-26 20:28:42
·
题解
upd:8.29一个细节挂了被撤回了。x,y ，不防钦定大小关系 x<y ，
则还需要满足 x+x>y 。
假设我们一开始就钦定最终的 x,y ，那么需要的代价是
\sum_i \min(|a_i-x|, |a_i-y|)
我们把数字全放在数轴上，这个式子的含义就是：在这个数轴上选取两个原点 (也就是上文中的x,y )，求和数轴上的点到这两个原点距离的较小值。x 点更近，而右半部分到达 y 更近。
如果满足 x+x>y 则直接更新答案，但这样得出的 x,y 并不一定满足 x+x>y 的要求。
如果不满足，则我们需要 x 向右调整，或者 y 向左调整。
如果 x 向右调整了 k 格，那么 y 能取到的范围可以确定，即
y<2\times(x+k)
而由于越靠近中位数，所求式子越小，我们可以直接令
y'=\min(y, 2\times(x+k)-1)
因此我们把调整后的代价看做一个函数 f(k) ，通过人类智慧可以猜出他是单谷函数，因此可以用三分解决。
f(k)=L(k)+R(k)
直到这里，我们可以设计程序了。
1.枚举一个分割点，分成左部分和右部分。
2.求出两部分的中位数，看看是否合法。
3.若合法，直接更新答案，否则三分求出最小的点，再更新。
但这题还有一个 corner case，若最终变成的 $x,y$ 其中**成为** $x$ 的只有一个数，则不需要 $x+x<y$ 的限制，特判掉即可。
有点省选联考 D1T1 的感觉。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5, inf=1e9;
using ll=long long;
int n, a[N];
ll ans=1ll*inf*inf, s[N];
ll calc(int l, int r, int x) {
int f=upper_bound(a+l, a+r+1, x)-a-1;
ll lp=f-l+1, rp=r-f;
return (lp*x-(s[f]-s[l-1]))+(s[r]-s[f]-rp*x);
}
void solve(int mid, int x, int y) {
int l=0, r=inf;
while(l+20<=r) {
int lp=l+(r-l)/3;
int rp=lp+(r-l)/3;
ll lans=(calc(1, mid, x+lp)+calc(mid+1, n, min(x+lp+x+lp-1, y))),
rans=(calc(1, mid, x+rp)+calc(mid+1, n, min(x+rp+x+rp-1, y)));
if(lans<rans) r=rp;
else l=lp;
}
ll res=1ll*inf*inf;
for(int i=l; i<=r; i++) {
res=min(res, calc(1, mid, x+i)+calc(mid+1, n, min(x+i+x+i-1, y)));
}
ans=min(ans, res);
return ;
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &a[i]);
sort(a+1, a+1+n);
for(int i=1; i<=n; i++)
s[i]=s[i-1]+a[i];
for(int i=1; i<n; i++) {
int x=a[i/2+1], y=a[(n-i+1)/2+i];
if(x+x>y) ans=min(ans, calc(1, i, x)+calc(i+1, n, y));
else solve(i, x, y);
}
ans=min(ans, calc(2, n, a[1+(n-1)/2]));
printf("%lld\n", ans);
return 0;
}
```