oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

Integer Intervals
Time Limit:1000MS? Memory Limit:10000K
Total Submit:960 Accepted:387

Description
An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input
The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output
Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

4
3 6
2 4
0 2
4 7

Sample Output

4
題目的意思是找一個(gè)集合 使這個(gè)集合包含上面每個(gè)集合的2個(gè)數(shù) 輸出集合個(gè)數(shù)
?策略：貪心
?實(shí)現(xiàn): 首先進(jìn)行預(yù)排序 即按照intervals的begin來(lái)對(duì)intervals排序
??? 然后貪心選擇每一個(gè)集合的盡量靠后的元素 因?yàn)檫@樣一定對(duì)后面的集合選擇有利（仔細(xì)體會(huì)一下吧)
????????? 比如第一個(gè)集合選最后兩個(gè)元素 后面的先檢查選出來(lái)的已經(jīng)有幾個(gè)在集合里面(0,1,2三中情況)仍選擇盡量靠后的??? 
??? 程序:
#include <stdio.h>
#include <stdlib.h>

struct interval
{
?int begin;
?int end;
}ii[10100];

int answer[20020];
int anslen;

int cmp(const void * a, const void * b)????? 
{
?return (*(interval*)a).end - (*(interval*)b).end;
}

int main()
{
?int nii;
?scanf("%d", &nii);
?int i;
?for(i=0; i<nii; i++)
?{
??scanf("%d%d", &ii[i].begin, &ii[i].end);
?}
?qsort(ii, nii, sizeof(ii[0]), cmp);
?answer[anslen++] = ii[0].end-1;
?answer[anslen++] = ii[0].end;
?i = 1;
?while(i<nii)????? 
?{
??int count = 0;
??if(answer[anslen-2] >= ii[i].begin && answer[anslen-2] <= ii[i].end) count++;
??if(answer[anslen-1] >= ii[i].begin && answer[anslen-1] <= ii[i].end) count++;
??if(count==0)
??{
???answer[anslen++] = ii[i].end-1;
???answer[anslen++] = ii[i].end;
??}
??else if(count == 1)
???answer[anslen++] = ii[i].end;
??i++;
?}
?printf("%d\n", anslen);
?return 0;
}
關(guān)于stdlib中qsort的用法 給你摘錄下
七種qsort排序方法 
<本文中排序都是采用的從小到大排序> 
一、對(duì)int類(lèi)型數(shù)組排序 
int num[100]; 
Sample: 
int cmp ( const void *a , const void *b ) 
{ 
???? return *(int *)a - *(int *)b; 
} 
qsort(num,100,sizeof(num[0]),cmp); 
如果num中的數(shù)據(jù)不是從0開(kāi)始的,比如1,那么應(yīng)該寫(xiě)num+1;

二、對(duì)char類(lèi)型數(shù)組排序（同int類(lèi)型）
char word[100]; 
Sample: 
int cmp( const void *a , const void *b ) 
{ 
??? return *(char *)a - *(char*)b; 
}
qsort(word,100,sizeof(word[0]),cmp)

三、對(duì)double類(lèi)型數(shù)組排序（特別要注意）
double in[100];
int cmp( const void *a , const void *b ) 
{ 
??? return *(double *)a > *(double *)b ? 1 : -1; 
} qsort(in,100,sizeof(in[0]),cmp)；
?
四、對(duì)結(jié)構(gòu)體一級(jí)排序 
struct In {
?double data; 
?int other; 
}s[100] 
//按照data的值從小到大將結(jié)構(gòu)體排序,關(guān)于結(jié)構(gòu)體內(nèi)的排序關(guān)鍵數(shù)據(jù)data的類(lèi)型可以很多種，
參考上面的例子寫(xiě) 
int cmp( const void *a ,const void *b) 
{ 
???? return (*(In *)a).data > (*(In *)b).data ? 1 : -1; 
} 
qsort(s,100,sizeof(s[0]),cmp); 

五、對(duì)結(jié)構(gòu)體二級(jí)排序 
struct In { 
?? int x; int y; 
}s[100]; 
//按照x從小到大排序，當(dāng)x相等時(shí)按照y從大到小排序 
int cmp( const void *a , const void *b ) 
{ 
??? struct In *c = (In *)a; 
??? struct In *d = (In *)b; 
??? if(c->x != d->x) return c->x - d->x; 
??? else return d->y - c->y; 
} 
qsort(s,100,sizeof(s[0]),cmp); 

六、對(duì)字符串進(jìn)行排序 
struct In { 
?? int data; char str[100]; 
}s[100]; 
//按照結(jié)構(gòu)體中字符串str的字典順序排序 
int cmp ( const void *a , const void *b ) 
{
??? return strcmp( (*(In *)a)->str , (*(In *)b)->str ); 
} 
qsort(s,100,sizeof(s[0]),cmp);