【题解】LA 3695【Distant Galaxy】

分析

这里考虑部分枚举,只枚举矩形的上下边界,用其他方法确定左右边界。
如图25:

对于竖线$i$,用$left[i]$表示竖线左边位于上下边界之上的点数,(不统计竖线上的点),用$on[i]$和$on2[i]$表示竖线上位于上下边界之间的点数($on[i]$不统计上下边界之上的点数,而另一个要统计)。这样给定左右边界,总点数为$left[j]-left[i]+on[i]+on2[j]$,当右边界确定时,$on[i]-left[i]$应最大。
枚举完上下边界之后,花费$O(n)$的时间计算上述数组们,然后枚举右边界$j$,同时顺手维护$on[i]-left[i]$的最大值。

代码

#include<cstdio>
#include<algorithm>
using std::sort;using std::unique;using std::max;
class Point{
public:
    int x,y;
    bool operator < (const Point &rhs) const{return x < rhs.x;};
};
const int MAXN = 100 + 6;
Point p[MAXN];
int n,m,y[MAXN],on[MAXN],on2[MAXN],left[MAXN];

int solve(){
    sort(p,p + n);sort(y,y + n);
    m = unique(y,y + n) - y;
    if(m <= 2) return n;

    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];

            int k = 0;
            for(int i = 0;i < n;i++){
                if(i == 0 || 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;

            int M = 0;
            for(int j = 1;j <= k;j++){
                ans = max(ans,left[j] + on2[j] + M);
                M = max(M,on[j] - left[j]);
            }
        }
    }
    return ans;
}

int main(){
    int id = 0;
    while(scanf("%d",&n) == 1 && 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",++id,solve());
    }

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注