看到您在BLOG的提问了 赶紧做了一下 写好了
题目是这样的
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);