洛谷3162 组装

题意简述：

　　在同一条线段上给定一些不同颜色的点

　　求一点使得每一个颜色中离它最近的点到它的距离的平方之和最小

　　（现在沉迷于画图qwq）

思路：

　　首先是数学推导这个很简单啦

　　设x为选的点的横坐标 a,b,c...为选中的不同颜色的点

　　则平方之和为 (a-x)²+(b-x)²+....

　　是一个二次函数啊 x=(a+b+...)/n时取得最小值最小值为 a²+b²+...-(a+b+...)²/n

　　到这里可以发现只要知道a,b,c....我们就可以求解了

　　于是最暴力的方法就是枚举a,b,c...所有的取值情况判断取min

　　这样子是30分的

　　优化一下：

　　我们从最左边开始处理

　　假设最初x取在最左边每种颜色自然是取离x最近的一点　就在这里优化

　　可以发现当一种颜色要换一个点的时候必然是过了这点和前一同色点的中点

　　然后我们就可以预处理出同色点变换的位置

　　然后在这种要变换的位置就可以求出两解（取左边的点和取右边的点）

　　和ans比较即可

　　但是如果每次求解都要重新计算那.......

　　所以我们可以记录 a+b+.... 与 a²+b²... 每次变换点的时候把这两个值稍作改变即可

CODE：

　　写得还算是比较顺利

　　但是最开始写的多开了几个数组然后RE了

　　然后借鉴了一下std里的处理挺巧的啊

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #define go(i,a,b) for(register int i=a;i<=b;i++)
 6 #define yes(i,a,b) for(register int i=a;i>=b;i--)
 7 #define ld long double
 8 #define M 200000+10
 9 using namespace std;
10 int read()
11 {
12     int x=0,y=1;char c=getchar();
13     while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();}
14     while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
15     return x*y;
16 }
17 int n,m,cnt;
18 ld s1,s2,ans1,ans2;
19 struct node1 {ld ps;int tp;} a[M];//position,type
20 struct node2 {ld nw,nt,sm;} b[M*2]; //now,type,sum
21 bool cmp1(node1 x,node1 y) {if(x.tp!=y.tp) return x.tp<y.tp;return x.ps<y.ps;}
22 bool cmp2(node2 x,node2 y) { return x.sm<y.sm;}
23 int main()
24 {
25     freopen("1.in","r",stdin);
26     freopen("1.out","w",stdout);
27     n=read();m=read();
28     go(i,1,m) {a[i].ps=read();a[i].tp=read();}
29     sort(a+1,a+m+1,cmp1);
30     go(i,1,m)
31     {
32         if(a[i].tp!=a[i-1].tp) {s1+=a[i].ps;s2+=a[i].ps*a[i].ps;continue ;}
33         b[++cnt].nw=a[i-1].ps;
34         b[cnt].nt=a[i].ps;
35         b[cnt].sm=(b[cnt].nw+b[cnt].nt)/(ld)2.0;
36     }
37     sort(b+1,b+cnt+1,cmp2);
38     ans1=s1;ans2=s2-s1*s1/(ld)n;
39     go(i,1,cnt)
40     {
41         ld x=b[i].nw,y=b[i].nt,sm;
42         s1-=x;s1+=y;
43         s2-=x*x;s2+=y*y;
44         sm=s2-s1*s1/(ld)n;
45         if(sm<ans2) {ans1=s1;ans2=sm;}
46     }
47     printf("%.4Lf",ans1/(ld)n);
48     return 0;
49 }

View Code

相关推荐