一、会场安排

将会场按结束时间从早到晚排序后，将最早活动结束时间作为该会场最开始活动，第二项为开始时间晚于第一项，但是结束时间最早的一项，以此类推，直至遍历所有活动。

索引剩余活动，重复上述操作，直至无活动剩余。

重复次数即为至少所需会场数目。

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

void sort(int data[], int num) {//将结束事件早的活动排在前面
	for (int i = 1;i < num;i = i + 2) {
		for (int j = 1;j < num - i - 1;j = j + 2) {
			if (data[j] > data[j + 2]) {
				int endTime = data[j];
				int startTime = data[j - 1];
				data[j] = data[j + 2];
				data[j - 1] = data[j + 1];
				data[j + 2] = endTime;
				data[j + 1] = startTime;
			}
		}
	}
}

//贪心算法寻找最少会场数目
int greedy(int data[], bool isArrange[], int num) {
	int count = 1;//设初始使用会场数目为1
	int endTime = data[1];//设置第一个活动的结束时间
	int i = 1;//设置当前指向活动，从第二项开始
	isArrange[0] = true;//将第一项活动状态改为已安排
	while (true) {
		bool flag = true;//用于判断是否全部活动都被安排
		for (int j = i * 2;j < num * 2;j = j + 2) {//从开始活动位置往后寻找
			if (isArrange[j / 2] == true) {//如果活动已被安排
				continue;
			}
			if (data[j] >= endTime) {//开始时间大于等于结束时间则可行
				isArrange[j / 2] = true;//设置为已安排
				endTime = data[j + 1];//更新结束时间
			}
		}
		for (;i < num;i++) {
			if (!isArrange[i]) {//当找到第一个未被安排时
				flag = false;
				endTime = data[2 * i + 1];//更新活动结束时间
				isArrange[i] = true;//更新安排
				count++;//需要的会场数增加
				break;
			}
		}
		if (flag == true) {
			break;
		}
	}
	return count;
}
int main() {
	ifstream ifs("input.txt", ios_base::binary);//输入文件位置
	ofstream ofs("output.txt", ios_base::binary);//输出文件位置
	int num = 0;//存储总活动数目
	int count = 0;//临时计数
	int* data = NULL;//存储活动区间
	bool* isArrange = NULL;//记录是否被安排
	if (!ifs) {
		return 1;
	}
	if (!ifs.eof()) {
		int  temp = 0;
		ifs >> temp;
		if (ifs.fail()) {
			ifs.clear();
			ifs.ignore(1);
		}
		num = temp;
	}
	data = new int[num * 2];
	isArrange = new bool[num];
	memset(isArrange, false, num * sizeof(bool));
	while (!ifs.eof()) {
		int temp = 0;
		ifs >> temp;
		if (ifs.fail()) {
			ifs.clear();
			ifs.ignore(1);
		}
		data[count] = temp;
		count++;
	}
	ifs.close();
	ifs.clear();
	sort(data, num * 2);
	count = greedy(data, isArrange, num);
	ofs << count;
	ofs.close();
	ofs.clear();
	return 0;
}

问题

如果使用链表来存储已排好序的活动数据，通过移除节点的方式可以让循环次数会大大降低，仅需要判断链表是否为空即可，而链表的第一项则是每一个会场的最开始的活动。

二、硬币找零

已知顾客与商家手中的硬币面值为

5分、1角、2角、5角、1元、2元（0.05，0.1，0.2，0.5，1，2）

商家手中硬币无限，而顾客手中硬币有限。

计算交易至少需要多少硬币数目，数目=顾客付的硬币数目+商家找回硬币数目

输入文件（input.txt）							输出文件(output.txt)
顾客手中硬币						应付金额	本次共需硬币数目（顾客+商家）
0.05	0.1	0.2	0.5	1	2
2	4	2	2	1	0	0.95	2 顾客付出：1枚1元硬币商家找回：1枚0.05元硬币
2	4	2	0	1	0	0.55	3 顾客付出： 1枚1元硬币+1枚0.05元硬币商家找回：1枚0.5元硬币

依据贪心算法的思路，用最大的硬币面额以及最接近的硬币面额两个条件，去计算。同时注意数目是否超过。

根据硬币数目，在顾客方寻找最接近的单个硬币金额，找到后相减，保证为值中的最大负数，则再从商家方用相同方式寻找最接近的单个硬币金额，相加，保证为值中的最小正数，则再次回到顾客方，直到金额为0。?

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

/*
数据格式
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
*/



int greedyCacl(int* data,float money) {
	float coin[] = { 0.05,0.1,0.2,0.5,1,2 };//对应金额
	int count = 0;//硬币数目
	bool flag = true;//true代表顾客，false代表商家
	int total = 0;//记录顾客手中的总钱数
	for (int i = 0;i < 6;i++) {
		total += coin[i] * data[i];
	}
	if (total < money) {//在硬币总金额小于应付款时，认为其无解
		return -1;//无解
	}
	else if (total == money) {//在硬币总金额等应付款时，全部给出
		for (int i = 0;i < 6;i++) {
			count += data[i];
		}
		return count;
	}

	//尽量用最大面额去支付
	//消去需要用多对枚硬币部分，留下金额使得至少有可用的硬币其面值超过该金额
	for (int i = 5;i >= 0;i--) {
		if (data[i] == 0) {
			continue;
		}
		int num = money / coin[i];//算得硬币数目
		if (num >= data[i]) {//大于或等于最大面额的硬币数目,则继续
			count = count + data[i];//记录硬币数目
			money = money - coin[i] * data[i];//求得剩余面额
			data[i] = 0;//清空
		}
		else {//如果当前面需要的数目大与应有数目，则记录不超过部分，并结束循环
			count = count + num;
			money = money - coin[i] * num;
			data[i] = data[i] - num;//减去已消耗部分
			break;
		}
	}
	//尽量用最接近但是超过或等于的硬币去支付
	while (abs(money) > 1e-6) {//当剩余金额为0时，则结束循环
		if (abs(money) < coin[0]) {//在金额小于最小面额时认为其无解
			return -1;//无解
		}
		float min = money;//记录最接近值
		int pos = 0;//记录位置
		if (flag) {//顾客付款
			for (int i = 5;i >= 0;i--) {//寻可行解
				if (data[i] == 0) {//为0则跳过
					continue;
				}
				float temp;//记录距离
				temp = money - coin[i];
				if (abs(temp) < 1e-6) {//等于0则结束
					pos = i;
					break;
				}
				else if (temp < -1e-6 && abs(temp) < min) {//距离需要为负，若比当前距离更近，则记录
					min = temp;
					pos = i;
				}
			}
			money = money - coin[pos];
			data[pos] = data[pos] - 1;
		}
		else {//商店找钱
			min = -min;//变为正数
			for (int i = 5;i >= 0;i--) {
				float temp;//记录距离
				temp = money + coin[i];
				if (abs(temp) < 1e-6) {//等于0则结束
					pos = i;
					break;
				}
				else if (temp > 1e-6 && temp < min) {//距离需要为正，若比当前距离更近，则记录
					min = temp;
					pos = i;
				}
			}
			money = money + coin[pos];
		}
		count = count + 1;
		if (money > 0) {
			flag = true;
		}
		else {
			flag = false;
		}
	}
	return count;
}

int main() {
	ifstream ifs("input.txt", ios_base::binary);//输入文件位置
	ofstream ofs("output.txt", ios_base::binary);//输出文件位置
	int count = 0;//用于临时计数
	int *data = new int[5];
	if (!ifs) {
		return 1;
	}
	//一行一行的计算数据
	while (!ifs.eof()) {

		float temp = 0;
		ifs >> temp;
		if (ifs.fail()) {
			ifs.clear();
			ifs.ignore(1);
		}
		if (count != 6) {//输入数据为每7个一行,由此断定输入完毕
			data[count] = temp;
			count++;
		}
		else {
			ofs << greedyCacl(data, temp) << endl;//输出
			count = 0;//清空
		}
	}
	ifs.close();
	ifs.clear();
	ofs.close();
	ofs.clear();
	return 0;
}