圆身（P9025 [CCC2021 S3] Lunch Concert） 题解
前言
昨天考试考到过了，顺便叫发题解，我的做法有两个，一个 \(O(n)\)，一个 \(O(n\log n)\)。
\(O(n\log mn)\) 的方法——三分
当时考试时就想到了，因为这次的答案是单谷函数，可以使用三分，跟二分差不多，就是找向左走上升还是向右走更优，然后 \(O(n)\) 统计一下这次走的花费
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T> inline void read(T &x) {
x = 0; char ch = getchar(); ll f = 1;
while (!isdigit(ch) && ch ^ '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); x *= f;
}
ll n,ans=1e16;
ll p[200005],w[200005],d[200005];
ll check(ll x){//计算花费
ll sum=0;
for(ll i=1;i<=n;i++){
if(p[i]<=x)
sum+=max(x-p[i]-d[i],0ll)*w[i];
else sum+=max(p[i]-x-d[i],0ll)*w[i];
}
ans=min(ans,sum);
return sum;
}
int main(){
read(n);
ll l=1e14,r=0;
for(ll i=1;i<=n;i++){
read(p[i]),read(w[i]),read(d[i]);
l=min(l,p[i]),r=max(r,p[i]);
}
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)>check(mid+1)) l=mid+1;
else r=mid-1;
}//三分
cout<<ans;
return 0;
}
接下来就是 \(O(n)\) 的算法。
\(O(n)\) 的方法
这个看起来是 \(O(n)\)，实际上却是 \(O(n\log n)\) 的，因为思路是 \(O(n)\)，但需要排序（说实话用个基数排序后就是正宗的 \(O(n)\)）。
我们发现，若这个音乐会正好开在某个人的范围内，那么这个人不需要移动，很明显这个范围的两个端点一定比跟内部的点更优。
那么就可以枚举每个人的左端点和右端点分别排序，并用预处理前缀和后缀进行快速计算当前点的答案。
6666