BZOJ3210: 花神的浇花集会

3210: 花神的浇花集会

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 238 Solved: 119
[Submit][Status]

Description

在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。

具体浇水活动详情请见BZOJ3153

但这不是重点

花神出了好多题，每道题都有两个参考系数：代码难度和算法难度

花神为了准备浇花集会的题，必须找一道尽量适合所有人的题

现在花神知道每个人的代码能力x和算法能力y，一道题（代码难度X算法难度Y）对这个人的不适合度为 Max ( abs ( X – x ) , abs ( Y – y ) )

也就是说无论太难还是太简单都会导致题目不适合做（如果全按花神本人能力设题，绝对的全场爆0的节奏，太简单，则体现不出花神的实力）

当然不是每次都如花神所愿，不一定有一道题适合所有人，所以要使所有人的不合适度总和尽可能低

花神出了100001*100001道题，每道题的代码难度和算法难度都为0，1，2，3，……，100000

Input

第一行一个正整数N，表示花神有N个学生，花神要为这N个学生选一道题

接下来N行，每行两个空格隔开的整数x[i],y[i]，表示这个学生的代码能力和算法能力

Output

一个整数，表示最小的不合适度总和

Sample Input

3

1 2

2 1

3 3

Sample Output

HINT

对于100%的数据，n<=100000,0<=x[i],y[i]<=100000

Source

mjmjmj命题Stilwell制作数据

题解：
类似于松鼠聚会，但本题不是单纯的取中位数就可以，因为这样如果取出的x‘和y’奇偶性不同是找不出满足条件的x，y的，所以我们可以在该解附近多找两个点，使奇偶性相同，来更新ans
代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000000000ll
 24 
 25 #define maxn 100000+5
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 struct rec{int x,y;ll z;}a[maxn];
 61 struct recc{ll x;int y;}b[10],c[10];
 62 const int d[7]={0,1,2,3,-1,-2,-3};
 63 int n;
 64 inline bool cmp1(rec a,rec b){return a.x<b.x;}
 65 inline bool cmp2(rec a,rec b){return a.y<b.y;}
 66 
 67 int main()
 68 
 69 {
 70 
 71     freopen("input.txt","r",stdin);
 72 
 73     freopen("output.txt","w",stdout);
 74 
 75     n=read();
 76     for1(i,n)
 77     {
 78         int x=read(),y=read();
 79         a[i].x=x+y;a[i].y=x-y;
 80     }
 81     sort(a+1,a+n+1,cmp1);
 82     for0(j,6)
 83     {
 84         b[j].y=a[(n+1)>>1].x+d[j];
 85         for1(i,n)b[j].x+=abs(a[i].x-b[j].y);
 86     }
 87     sort(a+1,a+n+1,cmp2);
 88     for0(j,6)
 89     {
 90         c[j].y=a[(n+1)>>1].y+d[j];
 91         for1(i,n)c[j].x+=abs(a[i].y-c[j].y);
 92     }
 93     ll ans=inf;
 94     for0(i,6)
 95      for0(j,6)
 96       if(((b[i].y&1)==(c[j].y&1)))ans=min(ans,b[i].x+c[j].x);
 97     printf("%lld
",ans>>1);
 98 
 99     return 0;
100 
101 }

View Code