8
5
2015
0

[BZOJ 3170][TJOI 2013]松鼠聚会

首先造几组数据,可以发现把每个点按x+y排序后取中位数,然后在中位数左右的点枚举,随机数据是卡不到的,而且我感到要构造数据很麻烦,所以就这么写了。

#include<cstdio>
#include<algorithm>
using namespace std;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
typedef long long LL;
#define debug
const int maxn=100100, canshu=500;
int mid, n;
struct yjq{
    int x,y;
    void read()
    {
        scanf("%d%d",&x,&y);
    }
};
yjq poi[maxn];
LL ans;
 
inline bool cmpx(yjq ac, yjq ak)
{
    return ac.x<ak.x;
}
 
inline bool cmp(yjq ac, yjq ak)
{
    return ac.x+ac.y<ak.x+ak.y;
}
 
inline bool cmpy(yjq ac, yjq ak)
{
    return ac.y<ak.y;
}
 
inline int dist(yjq ac, yjq ak)
{
    return max(abs(ac.x-ak.x),abs(ac.y-ak.y));
}
 
inline LL calcans(yjq ac)
{
    LL nowans=0;
    for (int j=1; j<=n; j++)
        nowans+=dist(ac,poi[j]);
    return nowans;
}
 
void baoli()
{
    for (int i=1; i<=n; i++)
    {
        ans=min(ans,calcans(poi[i]));
    }
    printf(lld"\n",ans);
}
 
int main()
{
    scanf("%d",&n);
    mid=(n+1)>>1;
    for (int i=1; i<=n; i++)
        poi[i].read();
    ans=0x3f3f3f3f3f3f3f3fLL;
#ifdef debug
    if (n<=1000)
    {
        baoli();
        return 0;
    }
#endif
    sort(poi+1,poi+1+n,cmp);
    ans=min(ans,calcans(poi[mid]));
    for (int i=1; i<=300; i++)
    {
        ans=min(ans,calcans(poi[mid+i]));
        ans=min(ans,calcans(poi[mid-i]));
    }
    printf(lld"\n",ans);
    fclose(stdout);
    return 0;
}
Category: 黑暗算法 | Tags: 黑暗算法

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com