今年暑假不AC Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2063 Accepted Submission(s): 1137
Problem Description
“今年暑假不AC？” “是的。” “那你干什么呢？” “看世界杯呀，笨蛋！” “@#$%^&*%...”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。 作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
Output
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
Sample Input
12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0
Sample Output
5
我的代码：：：：
#include<stdio.h>
struct d {
int start;
int end;
}; //选择用结构体
int main(){
struct d a[100],temp;
int i,j,n,count;
while(scanf("%d",&n)&&n){
for(i=0;i<n;i++)
scanf("%d%d",&a[i].start,&a[i].end);
for(i=0;i<n-1;i++)
for(j=0;j<n-1-i;j++)
if(a[j].end>a[j+1].end){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
temp.end=a[0].end;count=1;
for(i=1;i<n;i++)
if(a[i].start>=temp.end){
count++;
temp.end=a[i].end;
}
printf("%d ",count);
} return 0;
}
下面是摘抄！！！！留着看
贪心算法的几个经典例子
Time Limit:1000MS Memory Limit:65536K Total Submit:118 Accepted:49
Description
给定x 轴上n个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。
给定n个闭区间，计算去掉的最少闭区间数。
Input
输入数据的第一行是正整数n（n≤100），表示闭区间数。接下来的n行中，每行有2 个整数，分别表示闭区间的2个数端点。
Output
将计算出的去掉的最少闭区间数输出。
Sample Input
310 2010 1520 15Sample Output
2Source
#include <stdio.h>
#include <stdlib.h>
struct node
{
int l;
int r;
}s[101];
int cmp(const void*a,const void*b)
{
return (*(struct node*)a).r-(*(struct node*)b).r;
}
int main()
{
int i,n,t;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&s[i].l,&s[i].r);
if(s[i].l>s[i].r)
{
t=s[i].l;
s[i].l=s[i].r;
s[i].r=t;
}
}
qsort(s,n,sizeof(s[0]),cmp);
int star=s[0].r;
t=1;//第一个数据
for(i=1;i<n;i++)//循环选出最多的不想交的闭区间
{
if(s[i].l>star)
{
star=s[i].r;
t++;
}
}
printf("%d ",n-t);//总的区间数减去t就是去点的区间数了
2；会场安排问题
Time Limit:1000MS Memory Limit:65536K Total Submit:252 Accepted:76
Description
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。）
对于给定的k个待安排的活动，计算使用最少会场的时间表。
Input
输入数据的第一行有1 个正整数k（k≤10000），表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
Output
输出一个整数，表示最少会场数。
Sample Input
51 2312 2825 3527 8036 50
Sample Output
3
至今未能理解为什么要把开始和结束时间都排序。。
然后能连接在一起的就连接在一起。。不能的就要另开会场
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a, const void *b)
{
return *(int*)a > *(int*)b ? 1 : -1;
}
int arrange(int *begin, int *end, int s, int n)
{
int count = 0;
int i = s + 1;
if(n > 0)
{
count = 1;
for(; i < n; i++)//循环完后，可以在一起举行的，都来凝结在了一起给它一个会场，剩下的就每个会议分一个会场
{
if(begin[i] >= end[s])
{
s++;
}
else
{
count++;
}
}
}
return count;
}
int main()
{
int n,t;
int begin[10000];
int end[10000];
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d %d",&begin[i],&end[i]);
}
qsort(begin, n, sizeof(begin[0]), cmp);
qsort(end, n, sizeof(end[0]), cmp);
t=arrange(begin, end, 0, n);
printf("%d ",t);
return 0;
}
3
区间覆盖问题
Time Limit:1000MS Memory Limit:65536K Total Submit:106 Accepted:54
Description
设x1 , x2 ,…… , xn 是实直线上的n 个点。用固定长度的闭区间覆盖这n 个点，至少需要多少个这样的固定长度闭区间?
对于给定的实直线上的n个点和闭区间的长度k，设计解此问题的有效算法，计算覆盖点集的最少区间数，并证明算法的正确性。
Input
输入数据的第一行有2 个正整数n和k（n≤10000，k≤100），表示有n个点，且固定长度闭区间的长度为k。接下来的1 行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。
Output
输出一个整数，表示计算出的最少区间数输出。
Sample Input
7 3 1 2 3 4 5 -2 6
#include <stdio.h>
#include <stdlib.h>
int cmp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
}
int main()
{
int n,k,a[10000],i,p,t;
scanf("%d %d",&n,&k);
t=0;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(a,n,sizeof(a[0]),cmp);//从小到大排序
i=0;
while(i<n)
{
p=a[i]+k;
while(a[i]<=p)//能覆盖的就
i++;//下移
t++;//不能了区间加1
}
printf("%d ",t);
return 0;
}
Sample Output
3
下面是排序！！！！
1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循环的上下限*/
if(a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理简单，但其缺点是交换次数多，效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。
（2）“选择法”
选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /*给记号赋值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。
（3）“快速法”
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：
void quick(int *a,int i,int j)
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2]; /*选取的参照*/
do {
while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/
while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
if(m<=n) { /*若找到且满足条件，则交换*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /*运用递归*/
if(n>i) quick(a,i,n);
}
（4）“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。
void insert(int *a,int n)
{
int i,j,temp;
for(i=1;i<n;i++) {
temp=a[i]; /*temp为要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/
a[j+1]=a[j];
j--;
}
a[j+1]=temp; /*插入*/
}
}
（5）“shell法”
shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：
void shell(int *a,int n)
{
int i,j,k,x;
k=n/2; /*间距值*/
while(k>=1) {
for(i=k;i<n;i++) {
x=a[i];
j=i-k;
while(j>=0&&x<a[j]) {
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2; /*缩小间距值*/
}
}
上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。
#include<stdio.h>
/*别偷懒，下面的"..."代表函数体，自己加上去哦！*/
void bubble(int *a,int n)
{
...
}
void choise(int *a,int n)
{
...
}
void quick(int *a,int i,int j)
{
...
}
void insert(int *a,int n)
{
...
}
void shell(int *a,int n)
{
...
}
/*为了打印方便，我们写一个print吧。*/[code]
void print(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf(" ");
}
main()
{ /*为了公平，我们给每个函数定义一个相同数组*/
int a1[]={13,0,5,8,1,7,21,50,9,2};
int a2[]={13,0,5,8,1,7,21,50,9,2};
int a3[]={13,0,5,8,1,7,21,50,9,2};
int a4[]={13,0,5,8,1,7,21,50,9,2};
int a5[]={13,0,5,8,1,7,21,50,9,2};
printf("the original list:");
print(a1,10);
printf("according to bubble:");
bubble(a1,10);
print(a1,10);
printf("according to choise:");
choise(a2,10);
print(a2,10);
printf("according to quick:");
quick(a3,0,9);
print(a3,10);
printf("according to insert:");
insert(a4,10);
print(a4,10);
printf("according to shell:");
shell(a5,10);
print(a5,10);
}