P3162 [CQOI2012]组装

传送门

退火大法好

我并不会正解于是只好打退火了……其他没啥好讲……只要对每一种颜色开一个vector，存一下所有这个颜色的位置，判定的时候可以去所有的颜色里二分找到前缀和后缀，把和当前点距离小的加入答案

然后就没有然后了……

//minamoto
#include<bits/stdc++.h>
#define IT vector<int>::iterator
#define R register
#define double long double
#define RD T*(rand()*2-RAND_MAX)
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(R int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=1e4+5;const double D=0.97,eps=1e-14;
vector<int>pos[N];double ans=1e10,pp,pr,T,res,best,pq,hp;int n,m,x,c,mn=1e5+5,mx=-1e5+5;
IT it;
double calc(R double x){
    double r=0,p;
    fp(i,1,n){
        p=1e12;
        it=lower_bound(pos[i].begin(),pos[i].end(),x);
        if(it!=pos[i].end())p=min(p,(*it)-x);
        if(it!=pos[i].begin())p=min(p,x-*(it-1));
        r+=p*p;
    }return r;
}
int main(){
	srand(time(0));
//	freopen("testdata.in","r",stdin);
    n=read(),m=read();fp(i,1,m)x=read(),c=read(),pos[c].push_back(x),mn=min(mn,x),mx=max(mx,x);
    pr=(1.0*mn+mx)/2,best=calc(pr);
    while(clock()<CLOCKS_PER_SEC*0.5){
        hp=pp=pr,ans=best;
        for(T=100000;T>eps;T*=D){
            pq=pp+RD,res=calc(pq);
            if(best>res)best=res,pr=pq;
            if(ans>res||exp((ans-res)/T)>(double)rand()/RAND_MAX)
            ans=res,pp=pq;
        }if(pr==hp)break;
    }printf("%.4Lf
",pr);
}