題目描述：
給一個大小為n*m(n,m < 2000)的棋盤，有k(K<100,000)次操作。每次在位置（x,y）加入一個點，如果x,y已經有點了，那么加入的點需要滿足：
1. 與x,y的曼哈頓距離最近。
2. 如果滿足條件1的點有多個，那么要求x最小。
3. 如果滿足條件2的點有多個，那么要求y最小。
算法分析：
從x開始，對每行r暴力尋找與(r,y)距離最近的點。
如果使用并查集來維護，每行查找時間就是O(1)。
如果|x-r|大于現有最優值，那么現有最優值就是答案，停止查找。
最多查找的行數是sqrt(k)，也就是可能的最遠距離。
其實如果長寬高度差距較大，最遠距離可能很遠，但是查找行數就不會超過高度了。
如果高度比長度大，那么將棋盤翻轉就可以了。
總時間復雜度為O(K*sqrt(K))
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int N = 2005;
int P[N][N][2];
int n,m,t,ex,ey;
int dis(int x,int y){return abs(ex-x) + abs(ey-y);}
bool flag ;
int find(int x,int y,int p){return P[x][y][p] == y ? y : P[x][y][p] = find(x,P[x][y][p],p); }
inline void chk(int &ans, int nx, int ny,int &x, int &y){
int d = dis(nx,ny);
if(ans > d) {ans = d, x = nx, y = ny;}
else if(ans == d) {
if(!flag){
if(nx < x) {x = nx, y = ny;}
else if(nx == x && ny < y) {x = nx, y= ny;}
}
else {
if(ny < y) {x = nx, y = ny;}
else if(ny == y && nx < x) {x = nx;}
}
}
}
inline void update(int r, int& ans, int &x, int &y){
int nx = r, ny = find(r,ey,0);
if(ny <= m ){ chk(ans,nx,ny, x, y);}
ny = find(r,ey,1);
if(ny > 0 ){ chk(ans,nx,ny, x, y);}
}
int main(){
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
P[i][j][0] = P[i][j][1] = j;
scanf("%d%d%d",&n,&m,&t);
flag = 0; int cnt =0;
if(n>m) {swap(n,m); flag = 1;}
int test = 0;
while(t--){
int x ,y;
scanf("%d%d",&x,&y);
if(flag) swap(x,y);
ex = x, ey = y;
int d = 0, ans = ~0u>>2, nx, ny;
while(d <= ans && d<n) {
int r = x - d;
if(r > 0 && r <= n) update(r , ans, nx, ny);
r = x + d;
if(r > 0 && r <= n) update(r , ans, nx, ny);
d ++;
}
P[nx][ny][0] = ny+1;
P[nx][ny][1] = ny-1;
if(flag) swap(nx,ny);
printf("%d %d\n",nx,ny);
}
}
其中判斷的部分一定要盡量優，之前一直超時是因為沒用把判斷的函數設置為內聯函數。
posted on 2012-07-21 15:02
西月弦 閱讀(318)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告