SHAOXIAOJ-2624:贪心算法-活动安排问题

金币值：3 定数：6 时间限制：1.000 s 内存限制：128 M

正确：3 提交：8 正确率：37.50% 命题人：

点赞量：0 收藏量：0 题目类型：程序知识点：算法设计

设有n(1<=n<=20)个活动的集合E = {1, 2, …, n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi, 且si < fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si ≥ fj或sj ≥ fi时，活动i与活动j是相容的。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

#include <stdio.h>

struct action{
	int s;    //存储活动开始时间
	int f;   //存储活动结束时间
	int id;  //存储活动的编号 
	int x;  // x=1表示选择了该活动，否则表示没有选择该活动 
};

int fun(struct action a[],int n) {
	int i,j,sum;
	
	return sum;
}

void sort(struct action a[],int n) {
	int i,j;
	for(i=1; i<=n-1; i++) { // 按照活动的结束时间进行升序排序 
		for(j=1; j<=n-i; j++) {
			if(a[j].f>a[j+1].f) {
				struct action t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
}

int main(void) {
	int i,n;
        struct action a[21]; // 0号单元不存储有效数据
	scanf("%d", &n);
	for(i=1; i<=n; i++) {
		scanf("%d", &a[i].s);
	}
	for(i=1; i<=n; i++) {
		scanf("%d", &a[i].f);
	}
	for(i=1; i<=n; i++) {
		a[i].id=i;
	}
	sort(a,n);
	int sum=fun(a,n);
	printf("%d\n",sum);
	for(i=1; i<=n; i++) {
		printf("%d %d\n",a[i].id,a[i].x);
	}
	return 0;
}

第一行输入一个整数，表示有n个活动
第二行输入n个整数，分别表示每个活动的开始时间
第三行输入n个整数，分别表示每个活动的结束时间

第1行输出最大相容活动的个数
第2-n+1行每行输出两个整数（两个整数之间用一个空格隔开），第一个整数表示活动编号，第二个整数表示该活动是否被选中（1：表示选择了对应的活动，0表示没有选择对应的活动）。

11
1 3 0 5 3 5 6  8  8  2  12
4 5 6 7 8 9 10 11 12 13 14

2624: 贪心算法-活动安排问题

题目描述

测试代码复制

输入格式

输出格式

输入样例复制

输出样例复制