1.题目描述:点击打开链接
2.解题思路:本题要求找一个矩形,使得边上的点数最大。看上去比较棘手,如果只是单纯地枚举每行,每列,再加上要统计点数,时间复杂度会高达O(N^5),无法承受。因此,需要转变思路。
做了这么多题,会发现,这种带有统计目的的题目常常采用的策略就是先扫描,计算出一些必要的信息,例如前缀和等。将来处理时就能用O(1)时间得到想要的结果,便于寻找某种最优值。本题照样如此。对于竖线i,用Left[i]表示竖线左边位于上下边界上的点数(注意,不统计该竖线上的点)。on[i]和on2[i]统计竖线上位于上下边界之间的点数,但两者的区别在于on[i]不包含上下边界的点数,而on2[i]要统计。这样,如果给定了左右边界i,j时,矩形边界上的点数为Left[j]-Left[i]+on[i]+on2[j],(Left[j]-Left[i]有点类似于前缀和的意思)。而当右边界j确定时,on[i]-Left[i]应该最大。注意这里更新ans和on[i]-Left[i]的顺序,应该先更新ans,再更新on[i]-Left[i]。
3.代码:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<string> #include<sstream> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<functional> using namespace std; struct Point { int x, y; bool operator <(const Point&rhs)const { return x < rhs.x; } }; #define N 100+10 Point P[N]; int n, m, y[N], on[N], on2[N], Left[N]; int solve() { sort(P, P + n); sort(y, y + n); m = unique(y, y + n) - y;//所有不同的y坐标的个数 if (m <= 2)return n;//最多两种不同的y int ans = 0; for (int a = 0; a < m;a++) for (int b = a + 1; b < m; b++) { int ymin = y[a], ymax = y[b];//计算上下界分别是ymin,ymax时的解 int k = 0; for (int i = 0; i < n; i++) { if (!i || P[i].x != P[i - 1].x)//一条新的竖线 { k++; on[k] = on2[k] = 0; Left[k] = k == 0 ? 0 : Left[k - 1] + on2[k - 1] - on[k - 1]; } if (P[i].y>ymin&&P[i].y < ymax)on[k]++; if (P[i].y >= ymin&&P[i].y <= ymax)on2[k]++; } if (k <= 2)return n;//最多两种不同的x int M = 0; for (int j = 1; j <= k; j++) { ans = max(ans, Left[j] + on2[j] + M);//先更新ans,再更新M,因为更新ans用的是不含第j列的M值 M = max(M, on[j] - Left[j]); } } return ans; } int main() { //freopen("t.txt", "r", stdin); int rnd = 0; while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) { scanf("%d%d", &P[i].x, &P[i].y); y[i] = P[i].y; } printf("Case %d: %d\n", ++rnd, solve()); } return 0; }