10148 - Advertisement

[cpp] 
描述：區間選點問題，劉汝佳書上有這題，自己看看就會了 
#include <cstdio>  
#include <cstring>  
#include <cstdlib>  
int s[1010][2]; 
bool str[20010]; 
int cmp(const void *p1,const void *p2) 
{ 
    if(((int *)p1)[1] > ((int *)p2)[1]) return 1; 
    else if(((int *)p1)[1] < ((int *)p2)[1]) return -1; 
    else 
    { 
        if(((int *)p1)[0] > ((int *)p2)[0]) return -1; 
        else return 1; 
    } 
} 
int main() 
{ 
    //freopen("a.txt","r",stdin);  
    int t,n,m,x,y,min,max,p; 
    scanf("%d",&t); 
    while(t--) 
    { 
        min=20000,max=p=0; 
        memset(str,false,sizeof(str)); 
        scanf("%d %d",&n,&m); 
        for(int i=0; i<m; i++) 
        { 
            scanf("%d %d",&x,&y); 
            if(x>y) 
            { 
                int t=x; 
                x=y; 
                y=t; 
            } 
            x+=10000; 
            y+=10000; 
            s[i][0]=x; 
            s[i][1]=y; 
            if(y>max) max=y; 
            if(x<min) min=x; 
        } 
        qsort(s,m,sizeof(s[0]),cmp); 
        for(int i=0; i<m; i++) 
        { 
            x=s[i][0]; 
            y=s[i][1]; 
            int count=0; 
            for(int j=x; j<=y; j++) if(str[j]) count++; 
            for(int j=y; j>=x&&count<n; j--) 
                if(!str[j]) 
                { 
                    str[j]=true; 
                    p++; 
                    count++; 
                } 
        } 
        printf("%d\n",p); 
        for(int i=min; i<=max; i++) 
            if(str[i]) printf("%d\n",i-10000); 
        if(t) printf("\n"); 
    } 
    return 0; 
}