URAL 1019 - Line Painting

跟前面某个题一样，都是区间染色问题，还是用我的老方法，区间离散化+二分区间端点+区间处理做的，时间跑的还挺短

坑爹的情况就是最左端是0，最右端是1e9，区间求的是开区间

#include <stdio.h>   
#include <string.h>   
#include <math.h>   
#include <algorithm>   
using namespace std;  
typedef struct  
{  
    int l;  
    int r;  
    bool color;  
}seg;  
seg a[5005];  
int t[10005];  
int d[10005],ct;  
int f[10005];  
  
int find(int x,int n)  
{  
    int l=0,r=n-1,mid=(l+r)/2;  
    while(l<r)  
    {  
        if(x>d[mid])l=mid+1;  
        else r=mid;  
        mid=(l+r)/2;  
    }  
    return mid;  
}  
  
int main()  
{  
    int n;  
        scanf("%d",&n);  
        for(int i=0;i<n;i++)  
        {  
            char e;  
            scanf("%d %d %c",&t[2*i],&t[2*i+1],&e);  
            a[i].l=t[2*i];  
            a[i].r=t[2*i+1];  
            a[i].color=(e=='w')?0:1;  
        }  
        t[2*n]=0;t[2*n+1]=1e9;  
        sort(t,t+2*n+2);  
        ct=0;  
        d[ct++]=t[0];  
        for(int i=1;i<2*n+2;i++)  
            if(t[i]!=t[i-1])  
            d[ct++]=t[i];  
        memset(f,0,sizeof(f));  
        for(int i=0;i<n;i++)  
        {  
               int L=find(a[i].l,ct);  
               int R=find(a[i].r,ct);  
               for(int j=L;j<R;j++)  
                f[j]=a[i].color;  
        }  
        int left=0;  
        int max=0,a1,a2;  
        for(int i=0;i<ct;i++)  
        {  
            if(f[i]==1||d[i]==1e9)  
            {  
                if(left==d[i]){left=d[i+1];continue;}  
                else {  
                        if(d[i]-left>max){  
                                max=d[i]-left;  
                                a1=left;  
                                a2=d[i];  
                        }  
                        left=d[i+1];  
                }  
            }  
        }  
        printf("%d %d\n",a1,a2);  
    return 0;  
}  

补充：软件开发 , C++ ,

上一个：HDU4279(2012年天津网络赛---数论分析题)
下一个：快速组合数