jzoj6800-NOIP2020.9.19模拟spongebob【枚举】

正题

题目链接:https://gmoj.net/senior/#contest/show/3222/0

题目大意

$n$个$a_i,b_i$，求一个$x$使得最小化$$\sum _{i=1}^n|a_{i}x+b_i|$$

解题思路

每个$|a_{i}x+b_i|$可以视为一个分两段的函数，那么把所有加起来就是一个分$n+1$段的函数，枚举分段点然后每个段取最大值即可。

$code$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=3e5+10;
const double eps=1e-8;
int n,p[N],cnt;
double A,B,c[N],a[N],b[N],ans;
bool cmp(int x,int y)
{
    return c[x]<c[y];}
int main()
{
    freopen("spongebob.in","r",stdin);freopen("spongebob.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){
    scanf("%lf%lf",&a[i],&b[i]);if(fabs(a[i])>eps){
    c[i]=-b[i]/a[i],p[++cnt]=i;if(a[i]>0)a[i]=-a[i],b[i]=-b[i];}else b[i]=abs(b[i]);A+=a[i];B+=b[i];}sort(p+1,p+1+cnt,cmp);ans=1e18;double l=-1e18,r=c[p[1]];for(int i=1;i<=cnt;i++){
    if(l!=r){
    if(A>0)ans=min(ans,A*l+B);else ans=min(ans,A*r+B);}A-=2.0*a[p[i]];B-=2.0*b[p[i]];l=r;r=c[p[i+1]];}if(A>0)ans=min(ans,A*l+B);else ans=min(ans,A*r+B);printf("%lf",ans);
}