【bzoj2680】玩游戏1

2015.06.24 15:50 Wed | 32次阅读 | 旧日oi | 固定链接 | 源码

题目大意:

一开始平面上有2N个点,两个人轮流进行操作,每次操作,玩家可以将一个还未占领的点占领。
    最后玩家的得分为他占领的点两两之间的距离和。
小Z现决定挑战小K,为了显示自己无比NB的IQ,小Z决定让小K作为先手,而由于小K的光环过于强大,以至于小Z是屡战屡败。
     于是,小Z求助与你,在两人都采取最优策略情况下,他会与小K的分数差多少呢??

题解

令每个点的权值为这个点到所有点的距离之和/2,然后排序,贪心选就行了。
对于一对点(i,j),如果一个人i,j都选到了,那么i,j的距离在这个人的得分里一定算了,如果一人选一个,则一人得到了这条边一半的权值,相当于没选。而这样从大到小选一定是最优的。
我用另一个号交2444ms,换自己的号瞬间0ms,其他人最快1000+ms,我再交一次又2000ms+了……好魔性……,估计这个rank1不会有人破了……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
double w[1005],x[1005],y[1005],ans;
int n;
int main()
{
    int i,j;
    while(cin>>n)
    {
        n<<=1;
        for(i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]),w[i]=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            w[i]+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/2.0;
        sort(w+1,w+n+1);
        for(ans=0,i=n;i;i-=2) ans+=w[i]-w[i-1];
        printf("%.3lf\n",ans);
    }
}```