题目描述：
给一个大小为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
西月弦 阅读(316)
评论(0) 编辑 收藏 引用 所属分类:
解题报告