首页 > 代码库 > 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