GitBook

这里写图片描述 这里写图片描述

贪心算法 (虽然现在也不是很明白什么是贪心算法)

难点也就是对节目结束时间的排序 需要自己饶一饶

第一次写的时候还没学结构体 所以用数组写的比较长

#include<stdio.h>
int main() {
	int n,i,j,k,t;
	while(scanf("%d",&n),n!=0) {
		int re=1,result=1;
		int Ti_s[100],Ti_e[100];
		Ti_s[0]=Ti_e[0]=0;
		for(i=0; i<n; i++) {
			scanf("%d %d",&Ti_s[i],&Ti_e[i]);
			for(k=0; k<i; k++) {
				if(Ti_e[i]<Ti_e[k]) {
					t=Ti_e[k];
					Ti_e[k]=Ti_e[i];
					Ti_e[i]=t;
					t=Ti_s[k];
					Ti_s[k]=Ti_s[i];
					Ti_s[i]=t;
				}
			}

		}
//		for(i=0; i<n; i++) {
//			for(k=i+1,j=i; k<n; k++) {
//				if(Ti_e[j]<=Ti_s[k]) {
//					j=k;
//					re++;
//				}
//			}
//			if(re>result)
//				result=re;
//			if(i==0)
//				result=re;
//			re=1;
//		}
			for(k=1,j=0; k<n; k++) {
				if(Ti_e[j]<=Ti_s[k]) {
					j=k;
					re++;
				}
			}
		printf("%d\n",re);
	}
	return 0;
}

下面的是结构体的 但也是没有用sort

#include<stdio.h>
struct tv {
	int Ti_s;
	int Ti_e;
};
int main() {
	int i,k;
	int n,result;
	while(scanf("%d",&n),n!=0) {
		result=1;
		struct tv b[n],t;
		b[0].Ti_s=b[0].Ti_e=0;
		for(i=1; i<=n; i++)
			scanf("%d %d",&b[i].Ti_s,&b[i].Ti_e);
		for(i=1; i<=n; i++) {
			for(k=1; k<=n-i+1; k++) {
				if(b[k].Ti_e<b[k-1].Ti_e) {
					t=b[k];
					b[k]=b[k-1];
					b[k-1]=t;
				}
			}
		}
		for(i=2,t=b[1]; i<=n; i++) {
			if(b[i].Ti_s>=t.Ti_e) {
				result++;
				t=b[i];
			}
		}
		printf("%d\n",result);
	}
	return 0;
}

值得做的一题 题目地址:【杭电】[2037]今年暑假不AC接内容

在附一个优秀的讲解博文: HDU2037 今年暑假不AC 贪心算法