加载中…
个人资料
lovedream
lovedream
  • 博客等级:
  • 博客积分:0
  • 博客访问:60,165
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

POJ3657——二分,贪心,路径压缩

(2011-12-18 02:48:58)
标签:

杂谈

分类: ACM/ICPC解题报告

题意:有N<=1,000,000个数,未知。给出Q<=25,000个定义——”第S1——第S2个数中最小的数是A”,问有木有矛盾,若有矛盾,从第几个定义开始有矛盾。注意所有数均互不相等。

思路:二分答案,判断是否有矛盾。关键在于判断,我的方法是对A排序,对每个A,求各个区间的交,若不存在交或交集已完全被某些A”>A的区间染色了,则存在矛盾,否则将A的各个区间并起来染色,继续下一个最大的A”<A。

染色这里,线段树固然是很容易想到。但是100W太大,勉强可以。于是有了离散化,但是离散化太麻烦,可以用路径压缩来实现O(n)。

下面是代码,注意这份代码是不标准的,漏了一个判断(比如第1个数到第100个数里面最小值是1000000000,这个定义明显是错的,因为那是数的上限,而每个数都必须不同)。数据水了,网上的代码很多没有判断都过了,我的也删了比较短…

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int INF=1000000000;

int fa[1100000];
int q1[25500],q2[25500],A[25500];

struct Node
{
    int s,t,key;
}node[25500];

int cmp(const void *a,const void *b)
{
    return ((Node *)b)->key-((Node *)a)->key;
}

int ff(int n)
{
    if(n==fa[n])
        return n;
    return fa[n]=ff(fa[n]);
}
bool is(int x,int y)
{
    int i;
    for(i=y;i>=x;i--)
    {
        if(!fa[i])
            return 0;
        i=ff(i);
    }
    return 1;
}

void update(int x,int y)
{
    int i;
    for(i=y;i>=x;i--)
    {
        if(!fa[i])
            fa[i]=x;
        else
        {
            i=ff(i);
            if(i>x)
                fa[i]=x;
        }
    }
}

bool f(int n)
{
    int i,j,m1,m2,k;
    memset(fa,0,sizeof(fa));
    for(i=1;i<=n;i++)
        node[i].s=q1[i],node[i].t=q2[i],node[i].key=A[i];
    qsort(node+1,n,sizeof(Node),cmp);

    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n&&node[j].key==node[i].key;j++);
        j--;

        for(m1=0,m2=INF,k=i;k<=j;k++)
        {
            m1=m1>node[k].s?m1:node[k].s;
            m2=m2<node[k].t?m2:node[k].t;
        }
        if(m1>m2||is(m1,m2))
            return 0;
        for(k=i;k<=j;k++)
            update(node[k].s,node[k].t);
        i=j;
    }
    return 1;
}

int Bsearch(int N)
{
    int l=1,r=N,mid;
    if(f(N))
        return 0;
    while(l<r-1)
    {
        mid=(l+r)>>1;

        if(f(mid))
            l=mid;
        else
            r=mid;
    }
    if(!f(r-1))
        return r-1;
    return r;
}

int main()
{
    int N,Q,i;
   
    scanf("%d%d",&N,&Q);
    for(i=1;i<=Q;i++)
        scanf("%d%d%d",&q1[i],&q2[i],&A[i]);
    printf("%d\n",Bsearch(Q));
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有