首页 > 代码库 > LA 3695 Distant Galaxy
LA 3695 Distant Galaxy
给出n个点的坐标(坐标均为正数)，求最多有多少点能同在一个矩形的边界上。
题解里是构造了这样的几个数组，图中表示的很明白了。
首先枚举两条水平线，然后left[i]表示竖线i左边位于水平线上的点，on[i]表示位于竖线i上两条水平线之间(并不在水平线上)的点数，on2[i]表示位于竖线i上两条水平线之间加上水平线边界上的点数。
所以矩形框上的点数为：
left[j]-left[i]+on[i]+on2[j]
枚举右边界竖线j，j确定后维护on[i]-left[i]的最大值。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 100 + 10; 8 int n, m, y[maxn], on[maxn], on2[maxn], left[maxn]; 9 10 struct Point11 {12 int x, y;13 bool operator < (const Point& rhs) const14 {15 return x < rhs.x;16 }17 }p[maxn];18 19 int solve()20 {21 sort(p, p + n);22 sort(y, y + n);23 m = unique(y, y + n) - y; //m为不同y坐标的个数24 if(m <= 2)25 return n;26 27 int ans = 0;28 for(int a = 0; a < m; ++a)29 for(int b = a + 1; b < m; ++b)30 {31 int ymin = y[a], ymax = y[b];32 33 //计算left, on, on234 int k = 0; //k记录竖线的条数35 for(int i = 0; i < n; ++i)36 {37 if(i == 0 || p[i].x != p[i-1].x)38 { //这是一条新的竖线39 ++k;40 on[k] = on2[k] = 0;41 left[k] = k == 0 ? 0 : left[k-1] + on2[k-1] - on[k-1];42 }43 if(p[i].y > ymin && p[i].y < ymax)44 ++on[k];45 if(p[i].y >= ymin && p[i].y <= ymax)46 ++on2[k];47 }48 if(k <= 2)49 return n;50 51 int M = 0;52 for(int j = 1; j <= k; ++j)53 {54 ans = max(ans, left[j] + on2[j] + M);55 M = max(M, on[j] - left[j]);56 }57 }58 59 return ans;60 }61 62 int main(void)63 {64 #ifdef LOCAL65 freopen("3695in.txt", "r", stdin);66 #endif67 68 int kase = 0;69 while(scanf("%d", &n) == 1 && n)70 {71 for(int i = 0; i < n; ++i)72 {73 scanf("%d%d", &p[i].x, &p[i].y);74 y[i] = p[i].y;75 }76 printf("Case %d: %d\n", ++kase, solve());77 }78 return 0;79 }
小结：大白书上面的题感觉思路之奇妙，仔细琢磨也不能百分百领会其精髓。一定是我等弱渣太弱了，做题太少了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。