栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 3141 Distant Galaxy

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 3141 Distant Galaxy

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#define M(a) memset((a),0,sizeof((a)))#define maxn 110using namespace std;struct Point{    int x,y;    bool operator<(const Point & a)const    {        return x<a.x;    }}p[maxn];int n,m,y[maxn];int on[maxn];int on2[maxn];int lef[maxn];bool init(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%d%d",&p[i].x,&p[i].y);        y[i]=p[i].y;    }    return n;}int solve(){    sort(p+1,p+1+n);    sort(y+1,y+1+n);    m=unique(y+1,y+1+n)-y-1;    if(m<=2)return n;    int ans=0;    for(int a=1;a<=m;a++)    {        for(int b=a+1;b<=m;b++)        { int ymin=y[a],ymax=y[b]; int k=0; for(int i=1;i<=n;i++) {     if(i==1||p[i].x!=p[i-1].x)     {         k++;         on2[k]=on[k]=0;         lef[k]=k==1?0:lef[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,on2[j]+lef[j]+M);     M=max(M,on[j]-lef[j]); }        }    }    return ans;}int main(){      int ks=1;    while(init())    {        printf("Case %d: %dn",ks++,solve());    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/378650.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号