首页 > 代码库 > LA3695 Distant Galaxy
LA3695 Distant Galaxy
对于这种题真的是一点想法都没有,根本不知道从哪里下手。。。
还是大白上的题(P52),有详解。
书上说的枚举上下边界是指求出总共有多少种不同的纵坐标的值,因为题目中给出的坐标都是整数,每个纵坐标值都可以做为一个边界,这样就只有有限的组合。
还有一开始很困惑的地方就是,为什么求出的矩形都是特殊的矩形----与坐标轴平行的。值得仔细想想
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 105;typedef long long LL;struct point{ int x; int y; friend bool operator <(point a,point b) { return a.x<b.x; }}a[maxn];int y[maxn],on[maxn],on2[maxn],left[maxn];int solve(int n){ int m = unique(y,y+n)-y; if(m<=2)return n; int ans = 0; for(int low = 0;low<m;++low)for(int up = low+1;up<m;++up) { int ylow = y[low],yup = y[up],k = 0; for(int i = 0;i<n;++i) { if(i==0 || a[i].x!=a[i-1].x) { k++; on[k] = on2[k] = 0; if(k==1)left[k] = 0; else left[k] = left[k-1]+on2[k-1]-on[k-1]; } if(a[i].y>ylow && a[i].y<yup)on[k]++; if(a[i].y>=ylow && a[i].y<=yup)on2[k]++; } if(k<=2)return n; int t = 0; for(int i = 1;i<=k;++i) { ans = max(ans,left[i]+on2[i]+t); t = max(t,on[i]-left[i]); } } return ans;}int main(){// freopen("in.txt","r",stdin); int n,kase = 0; while(~scanf("%d",&n) && n) { for(int i =0;i<n;++i) { scanf("%d%d",&a[i].x,&a[i].y); y[i] = a[i].y; } sort(y,y+n); sort(a,a+n); printf("Case %d: %d\n",++kase,solve(n)); } return 0;}
LA3695 Distant Galaxy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。