oyjpArt ACM/ICPC算法程序設計空間

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
題目的意思是找一個集合 使這個集合包含上面每個集合的2個數 輸出集合個數
?策略：貪心
?實現: 首先進行預排序 即按照intervals的begin來對intervals排序
??? 然后貪心選擇每一個集合的盡量靠后的元素 因為這樣一定對后面的集合選擇有利（仔細體會一下吧)
????????? 比如第一個集合選最后兩個元素 后面的先檢查選出來的已經有幾個在集合里面(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;
}
關于stdlib中qsort的用法 給你摘錄下
七種qsort排序方法 
<本文中排序都是采用的從小到大排序> 
一、對int類型數組排序 
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中的數據不是從0開始的,比如1,那么應該寫num+1;

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

三、對double類型數組排序（特別要注意）
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)；
?
四、對結構體一級排序 
struct In {
?double data; 
?int other; 
}s[100] 
//按照data的值從小到大將結構體排序,關于結構體內的排序關鍵數據data的類型可以很多種，
參考上面的例子寫 
int cmp( const void *a ,const void *b) 
{ 
???? return (*(In *)a).data > (*(In *)b).data ? 1 : -1; 
} 
qsort(s,100,sizeof(s[0]),cmp); 

五、對結構體二級排序 
struct In { 
?? int x; int y; 
}s[100]; 
//按照x從小到大排序，當x相等時按照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); 

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