传送门

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;

}