CSU 2323 疯狂的企鹅II （中位数的性质）

Description

继在鹅厂工作的DJ训练完鹅厂的企鹅们之后，DJ发明了一个新游戏。该游戏在nxn的棋盘上进行，其中恰好有n个企鹅，企鹅向四个方向之一移动一格算作一步。DJ希望用最少的总步数把这些企鹅变成一排，即所有企鹅都在同一行或同一列(由于DJ目不斜视，他认为所有企鹅在同一对角线上的情况不算一列)。企鹅们为了避免DJ的毒打需要尽快排成一排，你能帮可怜的小企鹅们解决这个问题吗。注意任意时刻不能有两个企鹅在同一格。

Input

第一行一个整数n(n<=6*10^5)表明棋盘大小。接下来n行，每行两个整数Xi,Yi(1<=Xi,Yi<=n)，表示第i只企鹅的坐标。保证初始企鹅的坐标互不相同。

Output

一行一个整数表示最少需要的步数。

Sample Input

Sample Output

6

思路：
先放在同一列，或同一行，然后散开。
放在同一列时，位置选x坐标的中位数是最优解。
收到前期思路的影响，我的solve应该是写复杂了。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<vector>
  4 #include<stack>
  5 #include<queue>
  6 #include<map>
  7 #include<set>
  8 #include<cstdio>
  9 #include<cstring>
 10 #include<cmath>
 11 #include<ctime>
 12 #define fuck(x) cout<<#x<<" = "<<x<<endl;
 13 #define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;
 14 #define ls (t<<1)
 15 #define rs ((t<<1)|1)
 16 using namespace std;
 17 typedef long long ll;
 18 typedef unsigned long long ull;
 19 const int maxn = 600086;
 20 const int maxm = 600086;
 21 const int inf = 2.1e9;
 22 const ll Inf = 999999999999999999;
 23 const int mod = 1000000007;
 24 const double eps = 1e-6;
 25 const double pi = acos(-1);
 26 int n;
 27 int x[maxn],y[maxn];
 28 ll sumx[maxn],sumy[maxn];
 29 ll numx[maxn],numy[maxn];
 30 ll xx,yy,ansx,ansy;
 31 void solve(){
 32     ll sum=numx[n];
 33     for(int i=1;i<=n;i++){
 34         if(numx[i]>sum/2){
 35             xx=i;
 36             break;
 37         }
 38     }
 39 
 40     sum=numy[n];
 41     for(int i=1;i<=n;i++){
 42         if(numy[i]>sum/2){
 43             yy=i;
 44             break;
 45         }
 46     }
 47 
 48 
 49 //    fuck(xx)
 50     ansx=numx[xx-1]*xx-sumx[xx-1];
 51 //    fuck(ansx)
 52     ansx+=(sumx[n]-sumx[xx])-(numx[n]-numx[xx])*xx;
 53 //    fuck(sumx[n]-sumx[xx])
 54 
 55     ansy=numy[yy-1]*yy-sumy[yy-1];
 56     ansy+=(sumy[n]-sumy[yy])-(numy[n]-numy[yy])*yy;
 57 //    fuck(yy)
 58 
 59 }
 60 
 61 int main()
 62 {
 63 //    ios::sync_with_stdio(false);
 64 //    freopen("in.txt","r",stdin);
 65 
 66 
 67     scanf("%d",&n);
 68     for(int i=1;i<=n;i++){
 69         scanf("%d%d",&x[i],&y[i]);
 70     }
 71     sort(x+1,x+n+1);
 72     sort(y+1,y+n+1);
 73 
 74 
 75 
 76     int tot=1;
 77     for(int i=1;i<=n;i++){
 78         sumx[i]=sumx[i-1];
 79         numx[i]=numx[i-1];
 80         while (x[tot]==i){
 81             sumx[i]+=i;
 82             numx[i]++;
 83             tot++;
 84         }
 85     }
 86 
 87 //    for(int i=1;i<=n;i++){
 88 //        cout<<sumx[i]<<" ";
 89 //    }
 90 //    cout<<endl;
 91 
 92     tot=1;
 93     for(int i=1;i<=n;i++){
 94         sumy[i]=sumy[i-1];
 95         numy[i]=numy[i-1];
 96 
 97         while (y[tot]==i){
 98             sumy[i]+=i;
 99             numy[i]++;
100             tot++;
101         }
102     }
103     solve();
104     ll ans=Inf;
105 
106 //    fuck(ansx)fuck(ansy)
107     ll ans1,ans2;
108     ans1=ans2=0;
109 
110     for(int i=1;i<=n;i++){
111         ans1+=abs(i-x[i]);
112         ans2+=abs(i-y[i]);
113 //        fuck(x[i])
114     }
115 
116     ans=min(ans1+ansy,ans2+ansx);
117 
118     printf("%lld
",ans);
119 
120 
121     return 0;
122 }
123 
124 /**********************************************************************
125     Problem: 2323
126     User: 232574
127     Language: C++
128     Result: AC
129     Time:520 ms
130     Memory:25464 kb
131 **********************************************************************/

View Code