NC19924. [CQOI2012]组装
描述
输入描述
输入第一行为两个整数n, m，即零件的种类数和生产车间的个数。以下m行每行两个整数xi和pi（1 ≤ pi ≤ n）。输入按照生产车间从左到右的顺序排列（即xi ≤ xi+1。注意车间位置可以重复）。输入保证每种零件都有车间生产。
输出描述
输出仅一行，即组装车间的最优位置（可以和某个生产车间重合），四舍五入保留四位小数。输入保证最优位置惟一。
示例1
输入:
3 5 -1 3 0 1 2 3 4 2 5 2
输出:
2.0000
C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 1508K, 提交时间: 2020-03-28 23:57:38
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 10010
using namespace std;
int n,m,x,y,point[N],cnt,f[N];
double P,S,ans,t;
struct use
{
int a,b,v;
}e[N*20];
bool cmp(use a,use b)
{
return a.v<b.v;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(!f[y]) point[y]=x,f[y]=1,P+=(double)x*x,S+=(double)x;
else
{
e[++cnt]=use{point[y],x,(point[y]+x)};
point[y]=x;
}
}
ans=P-(S*S)/(double)n;
t=S/(double)n;
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
{
double t1=P,t2=S;
double temp;
t1=(double)(t1-(double)e[i].a*e[i].a+(double)e[i].b*e[i].b);
t2=(double)(t2-(double)e[i].a+(double)e[i].b);
temp=(t1-(t2*t2)/(double)n);
P=t1;
S=t2;
if(temp<ans)
{
ans=temp;
t=S/(double)n;
}
}
printf("%.4lf\n",t);
}