新手,第一次做这类题目,wa了好多次,故写个题解来总结一下,如有不正之处,欢迎交流。
算法
(二分+前缀和+离散化) $O(n^2logn)$
思路:
第一眼,矩阵,正方形覆盖,想到了二维前缀和;答案最小化,猜想可以二分,容易证明。
于是乎,最简单的想法就是:预处理前缀和,二分判定答案。
但本题的特点在于,数据数量少,但范围较大,怎么办?离散化。
(离散化没做过多少题目,这里写详细一点。)
离散化
本题需要进行预处理,手段是离散化。我们在处理二维前缀和的时候,很多空间是浪费的(有点稀疏矩阵的意思?),故而,我们可以只保留出现过值的行与列,然后用数学推导来确定某个正方形的和。
我们离散化横纵坐标(我是将横纵坐标分开来处理),并且对每个位置值建立一个值到位置的映射(用空间换一点时间)。
离散化的问题在于,我们原先可以使用如下的公式计算出正方形的和:$s[x][y]-s[x-r][y]-s[x][y-r]+s[x-r][y-r]$,但现在我们没办法直接使用上述公式。不过这也是好处理的,我们只需要二分查找对应坐标上小于等于x-r/y-r的最大位置px/py,用$s[px][y]$(或$s[x][py]$)代替上式中对应的位置即可,这一结论是显然的。
至此,我们通过离散化将空间复杂度降低至$o(n^2)$(看到有人使用一维数组,但我还没看懂)。对于查找,我们的复杂度为$o(logn)$。
二分
本题其实最核心的是二分(不过也是最简单的部分了)。由于半径可以任意大(在最优解的右侧都为可行域),我们可以发现最优解必然处于可行解的边界上。为了最小化可行解,我们使用$r=mid$型的二分(见lyd书)。
时间复杂度
最终,我们算法的复杂度可以想见主要在二分上(预处理的复杂度不占主导地位),二分一次的复杂度为$O(n^2)$(实际上还要二分搜一下合适的位置,但可以看成一个常数),总共的时间复杂度为$O(n^2logn)$。
参考文献
无
C++ 代码
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define oj
const int maxn = 510;
int s[maxn][maxn];
int x[maxn],y[maxn];
int xnum[10000+10], ynum[10000+10];
int l1, l2;
int c,n;
vector<pair<int, int>> ma;
void gets(){
for (int i=1; i<=l1; i++) {
for (int j=1; j<=l2; j++) {
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
}
inline int getpos(int * tem,int len,int k){
int l = 0, r = len;
while (l<r) {
int mid = (l + r + 1) >> 1;
if(tem[mid]<=k)
l = mid;else {
r = mid - 1;
}
}
if(l==0)
return -1;
else {
return l;
}
}
void uni(){
sort(x + 1, x +n + 1);
l1 = unique(x + 1, x + n + 1) - (x+1);
for (int i=1; i<=l1; i++) {
xnum[x[i]] = i;
}
sort(y + 1, y + n + 1);
l2 = unique(y + 1, y + n + 1) - (y+1);
for (int i=1; i<=l2; i++) {
ynum[y[i]] = i;
}
}
inline bool check(int i,int j,int r){
bool fx = (x[i] > r), fy = (y[j] > r);
//printf("x:%d y:%d", x[i], y[i]);
int ans = s[i][j];
int px = -1, py = -1;
if(fx){
px = getpos(x, l1, x[i]-r);
if(px!=-1){
ans -= s[px][j];
}
}
if(fy){
py = getpos(y, l2, y[j]-r);
if(py!=-1){
ans -= s[i][py];
}
}
if(px!=-1&&py!=-1)
ans += s[px][py];
//cout <<fx<<" "<<fy<<" "<<px<<" "<<py<<" "<< r<<" "<<ans << endl;
return ans >= c;
}
int main(){
#ifndef oj
freopen("data.in", "r", stdin);
freopen("oj.out", "w", stdout);
#endif
cin >> c >> n;
memset(s, 0, sizeof s);
for (int i=1; i<=n; i++) {
int a, b;
scanf("%d%d", &a, &b);
x[i] = a, y[i] = b;
ma.push_back(make_pair(a, b));
}
uni();
for (int i=0; i<ma.size(); i++) {
s[xnum[ma[i].first]][ynum[ma[i].second]]++;
}
gets();
int r = 10000 + 1, l = 1;
while (l<r) {
int mid = (l + r) >> 1;
bool ok = 1;
for (int i=1; ok&&i<=l1; i++) {
for (int j=1; ok&&j<=l2; j++) {
if(check(i, j, mid))
ok = 0;
}
}
if(!ok){
r = mid;
}else{
l = mid + 1;
}
}
cout << l << endl;
return 0;
}