C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Ural 1019. Line Painting 解题报告

Posted on 2012-01-18 00:42 C小加 阅读(1928) 评论(6)  编辑 收藏 引用 所属分类: 解题报告
离散化+朴素算法。当然用线段树也可以过,我主要是想练习一下离散化,所以直接朴素了(更新5000次以内,离散化后的长度1万以内)。谁会想到半夜这个时候我居然在切题。第二次写离散化,可能与第一次隔的时间有点长,写的一塌糊涂。大家眼中的水题被我搞得人不像人,鬼不像鬼。好失落。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline int L(int r){return r<<1;}
inline int R(int r){return ((r<<1)+1);}

const int MAXM=5003;
typedef struct
{
    int zy,value;
}line;
line node[MAXM*2];
int post[MAXM][2];
char col[MAXM][2];
int l[MAXM*2];
int zz[MAXM*2];

void ranse(int b,int e,int c)
{
    for(int i=b;i<e;i++)
    {
        l[i]=c;
    }
}
bool cmp(line l1,line l2)
{
    return l1.value<l2.value;
}

int main()
{
    int n;
    scanf("%d",&n);
    post[0][0]=0;
    post[0][1]=1000000000;
    col[0][0]='w';
        node[L(0)].zy=-0-1;//左值为负
        node[R(0)].zy=0+1;//右值为正
        node[L(0)].value=post[0][0];//把左右界坐标真值储存在结构体数组中
        node[R(0)].value=post[0][1];

    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %s",&post[i][0],&post[i][1],col[i]);
        //getchar();
        node[L(i)].zy=-i-1;//左值为负
        node[R(i)].zy=i+1;//右值为正
        node[L(i)].value=post[i][0];//把左右界坐标真值储存在结构体数组中
        node[R(i)].value=post[i][1];
    }
    sort(node,node+(n+1)*2,cmp);//对所有坐标进行排序
    int count=0,temp=node[0].value;//count为离散化后坐标值。
    for(int i=0;i<2*(n+1);i++)
    {
        if(node[i].value!=temp)//如果坐标不同,则坐标加1
        {
            count++;
            temp=node[i].value;
        }

        if(node[i].zy<0) post[-node[i].zy-1][0]=count;//新post为离散化过后,左右界值
        else post[node[i].zy-1][1]=count;
        zz[count]=node[i].value;
    }
    memset(l,0,sizeof(l));
    l[count]=1;
    for(int i=0;i<=n;i++)
    {
        if(col[i][0]=='w') ranse(post[i][0],post[i][1],0);
        else ranse(post[i][0],post[i][1],1);
    }
    int sum=0;
    int ans=0;
    int z,y,ansz,ansy;
    for(int i=0;i<=count;i++)
    {
        if(l[i]==0)
        {
            if(sum==0) z=zz[i];
             sum++;
        }
        else
        {

            if(sum!=0)
            {
                y=zz[i]-z;
                if(y>ans)
                {
                    ans=y;
                    ansz=z;
                    ansy=zz[i];
                }
                sum=0;
            }

        }
    }
    printf("%d %d\n",ansz,ansy);
    return 0;
}

Feedback

# re: Ural 1019. Line Painting 解题报告[未登录]  回复  更多评论   

2012-01-18 09:32 by 春秋十二月
有潜力,思维能力不错,但觉得你的程序还缺乏工业强度,继续努力

# re: Ural 1019. Line Painting 解题报告  回复  更多评论   

2012-01-18 21:45 by C小加
谢谢,我会继续努力的。还没见过工业代码。@春秋十二月

# re: Ural 1019. Line Painting 解题报告  回复  更多评论   

2012-05-17 17:42 by PaceLeola
Some time before, I needed to buy a house for my organization but I did not have enough cash and could not order something. Thank goodness my sister proposed to try to take the <a href="http://goodfinance-blog.com">loan</a> from trustworthy bank. Therefore, I did so and was satisfied with my financial loan.

# re: Ural 1019. Line Painting 解题报告  回复  更多评论   

2013-04-22 21:06 by up here
If you are in a rush and have no clue how to gain some spare time so as to generate first-rate resume, contact companies that propose to buy CV.

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理