[CQOI2012]组装 (贪心)

CQOI2012]组装

solution:

蒟蒻表示并不会模拟退火,所以用了差分数组加贪心吗。我们先来看题:

  1. 在数轴上的某个位置修建一个组装车间
  2. 到组装车间距离的平方的最小值。
  3. 1<=n<=20000

心路历程:

  1. 在一条直线上
  2. 距离的平方?(二次函数?)
  3. 1<=n<=10000?(nlogn(logn.....)?)

嗯?乍一看还真不知道怎么做啊!

可是在x轴上?还要距离的平方,好像几个二次函数加一起还是二次函数来着?

莫非?这整体就是一个单峰函数?

好吧,零件种类有多种,但(既然是平方)应该还是要从二次函数出手吧。

既然每种物资只能选一个的话那干脆写一个分段函数吧。|xi|<=200000,他给的又是整形,分界点最多只有400000个,好像可行

所以:

贪心:它的范围是-100000~100000,但如果我们将一个零件看成一个二次函数,数轴看成x轴,因为他们都是平方,每个零件所构成的函数都是\(y={(x+k)}^2\)的形式(k表示零件在数轴上的位置)。

所以对于每一类零件,建立一个坐标轴,将零件画成二次函数的形式,这样对于每一个x值,我们贪心的选y值最小的那个零件。这样就能构成一个分段函数,而我们将每一种类的零件所构成的分段函数放在一起(用差分数组维护\(y=ax^2+bx+c\) 中的b与c),几个二次函数加一起还是二次函数,虽然分的段特别多,但绝对在我们的承受范围内,然后我们用二次函数求最小值的公式把最小值求出来即可(最小值可以在段外!!!)

零件位置给的是整形,分段的点的小数部分绝对为0或0.5,我们在差分数组前先处理一下(乘个二,加上200001,避免负数)(当然!你也可以用莫对思想维护!(比如鸽王发的那篇题解))

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define db double
#define rg register int
using namespace std;
struct su{
    int x,y;
}t[200005];

int n,m,l,r;
ll s[800015];
ll v,k[800015];//请不要吝啬您的long long和double
db a,b,c,res=(ll)1<<50,ans,tot;//res初值赋大些

inline bool cmp(su x,su y){
    return x.y==y.y?x.x<y.x:x.y<y.y;
}

int main(){
    //freopen("battle.in","r",stdin);
    //freopen("battle.out","w",stdout);
    cin>>n>>m;a=n;
    for(rg i=1;i<=m;++i)
        cin>>t[i].x>>t[i].y;
    sort(t+1,t+m+1,cmp);
    for(rg i=1;i<=m;++i){
        if(t[i].y!=t[i-1].y)l=1;
        else l=t[i].x+t[i-1].x+400001;
        if(t[i].y!=t[i+1].y)r=800002;
        else r=t[i].x+t[i+1].x+400001;
        v=-2*t[i].x;s[l]+=v;s[r]-=v;
        v>>=1;v=v*v;k[l]+=v;k[r]-=v;
    }
    for(rg i=1;i<=800001;++i){
        b=b+s[i];c=c+k[i];tot=c-(b*b)/(4*a);
        if(tot<res)res=tot,ans=-b/(2*a);
    }printf("%.4lf",ans);
    return 0;
}
上一篇:递推与递归专题练习


下一篇:codeforces contest 1111