mdzz,为什么这题有个贪心的标签啊qwq
首先考虑每一种车间,对于每相邻两个车间,在中点左边那么左边那个会贡献答案,在右边就右边那个更优
所以总共会有m-1个这样的分界中点,然后最多有m+1个(头尾也算)区间,满足在区间内选点其他的贡献答案的车间是固定的
假设贡献答案的车间是固定的,考虑拆答案柿子\(\sum_{i=1}^{n}(x-x_i)^2=nx^2-2x\sum x_i+\sum {x_i}^2\),就是二次函数求区间最小值
然后从左往右扫,维护\(\sum x_i\)和\(sum {x_i}^2\)救星了
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=2e5+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL a[N];
int b[N],bk[N];
struct node
{
int i,j;
bool operator < (const node &bb) const {return a[i]+a[j]<a[bb.i]+a[bb.j];}
}qq[N];
int n,m,q;
db ma=1e20,ans,na,nb,nc;
il void gmin(db a,db b,db c,db l,db r)
{
if(a*l*l+b*l+c<ma) ma=a*l*l+b*l+c,ans=l;
db x=-b/a/2;
if(x>=l&&x<=r&&a*x*x+b*x+c<ma) ma=a*x*x+b*x+c,ans=x;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=m;++i)
{
a[i]=rd(),b[i]=rd();
if(bk[b[i]]) qq[++q]=(node){bk[b[i]],i};
else nb-=2*a[i],nc+=(db)a[i]*a[i];
bk[b[i]]=i;
}
sort(qq+1,qq+q+1);
a[0]=-1e9,a[m+1]=1e18,a[m+2]=a[m+1]+1;
qq[++q]=(node){m+1,m+1},qq[q+1]=(node){m+2,m+2};
na=n;
for(int i=1,j=1;i<=q;i=j)
{
db l=(db)(a[qq[i-1].i]+a[qq[i-1].j])/2,r=(db)(a[qq[j].i]+a[qq[j].j])/2;
while(!(qq[i]<qq[j]))
{
gmin(na,nb,nc,l,r);
nb+=2*a[qq[j].i],nc-=(db)a[qq[j].i]*a[qq[j].i];
nb-=2*a[qq[j].j],nc+=(db)a[qq[j].j]*a[qq[j].j];
++j;
}
}
printf("%.4lf\n",ans);
return 0;
}