[ACM实验六]ACM程序设计基础（4）

杰拉斯 | 时间：2012-05-22, Tue | 16,733 views
编程算法　

实验项目：ACM程序设计基础(4)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.设有n个活动的集合E={1,2,…n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且Si<Fi，求出最多可以安排多少个活动使用该资源，并给出一个安排方案，如：

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

最多安排的资源个数为4，安排方案为：11 2 8 1
Sample Input
11 12 14 5 7 0 6 3 5 8 12 5 9 2 13 8 11 3 8 6 10 1 4
Sample Output
11 2 8 1 (4)
2.用KMP算法实现实验，输入两个只包含小写字母的字符串，判断第二个字符串是否是第一个字符串的子串，是则输出第二字符串在第一个字符串的起始位置，不是则输出NO。例如：
输入：abedsadfdseg
dsa
输出：4
3. Crashing Balloon问题，见Crashing Balloon。

1.设有n个活动的集合E={1,2,…n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且Si<Fi，求出最多可以安排多少个活动使用该资源，并给出一个安排方案。

这道题明显用贪心算法，每次只要先举办最早结束的活动，就能挤出更多的时间来进行其它活动，即按结束时间排序，取第一个活动，然后每次去开始时间大于等于上一个结束时间的活动，每取一个活动计数器加一，最终得出的便是题目所求答案。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct T{
	int i;
	int s;
	int f;
	bool operator <(const T t){
		return f < t.f;
	}
};

int main(){
	T t;
	int n, i, num = 0, endtime = 0;
	vector<T> v;
	scanf("%d", &n);
	for(i = 0; i < n; ++i){
		int s, f;
		scanf("%d%d", &s, &f);
		t.i = i + 1;
		t.s = s;
		t.f = f;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	for(i = 0; i < n; ++i){
		if(v[i].s >= endtime){
			++num;
			endtime = v[i].f;
			printf("%d ", v[i].i);
		}
		//printf("%d %d %d\n", v[i].i, v[i].s, v[i].e);
	}
	printf("(%d)\n", num);
	return 0;
}

2.用KMP算法实现实验，输入两个只包含小写字母的字符串，判断第二个字符串是否是第一个字符串的子串，是则输出第二字符串在第一个字符串的起始位置，不是则输出NO。

KMP算法等有空另开一文详细研究下，最近很多要操心的事，暂时先不讲思路了。。

#include<iostream>
#include<string>
using namespace std;

int getIndex(string str, string sub){
	int i = 1, j = 0, next[100];
	next[1] = 0;
	str = " " + str;
	sub = " " + sub;
	while(i < sub.length()){
		if(j == 0 || sub[i] == sub[j]){
			++i;
			++j;
			next[i] = j;
		}else{
			j = next[j];
		}
	}
	i = 1;j = 1;
	while(i < str.length()){
		if(j == 0 || str[i] == sub[j]){
			++i;
			++j;
		}else{
			j = next[j];
		}
		if(j >= sub.length())
			return i - sub.length() + 1;
	}
	return -1;
	cout << str << endl;
	cout << sub << endl;
	cout << " ";
	for(i = 1; i < sub.length(); ++i){
		cout << next[i];
	}
	cout << endl;
}

int main(){
	string str = "abedsadfdseg", sub = "dsa";
	cout << getIndex(str, sub) << endl;
	return 0;
}

3. Crashing Balloon问题，详见Crashing Balloon。

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客