凑钱

一.题目

二.思想

1.使用合并排序，稳定，也可以选择快排，但不稳定。也可以在一定数量下使用插入排序，在一定数量下使用其他高效率的排序方法。

2.使用二分查找最接近目标值的数。

三.代码ps：审题没审清，题目给出的每种面额的money张数是不限的。下面代码是限制的，前面n个数是张数，后面n个是面额。但做法都是一样的。

#include<stdio.h>
#include<malloc.h>
typedef struct {
	int count;
	int money;
}arr;

int target;
int count = 0;
int n;
arr* list;

void merge(arr* temp, int left, int mid, int right) {
	int l_pos = left;
	int r_pos = mid + 1;
	int pos = left;
	while (l_pos <= mid && r_pos <= right) {
		if (list[l_pos].money < list[r_pos].money)
			temp[pos++] = list[l_pos++];
		else
			temp[pos++] = list[r_pos++];
	}
	while (l_pos <= mid)
		temp[pos++] = list[l_pos++];
	while (r_pos <= right)
		temp[pos++] = list[r_pos++];
	while (left <= right) {
		list[left] = temp[left];
		left++;
	}
}

void sort(arr* temp, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		sort(temp, left, mid);
		sort(temp, mid + 1, right);
		merge(temp, left, mid, right);
	}
}

void mergeSort() {
	arr* temp = (arr*)malloc(sizeof(arr) * n);
	if (temp != NULL) {
		sort(temp, 0, n - 1);
		free(temp);
	}
}

void init() {
	printf("请输入目标值target：");
	scanf("%d", &target);
	printf("请输入面值种类n：");
	scanf("%d", &n);
	printf("请输入张数与面值：");
	list = (arr*)malloc(sizeof(arr) * n);
	for (int i = 0; i < 2 * n; i++) {
		if (i < n)
			scanf("%d", &list[i].count);
		else
			scanf("%d", &list[i % n].money);
	}
	mergeSort();
}

int findNum(int left,int right,int target) {
	if (left == right)
		return left;
	int mid = (left + right) / 2;
	if (list[mid].money < target)
		findNum(mid + 1, right, target);
	else
		findNum(left, mid - 1, target);
}

void match() {
	int right = n - 1;
	while (right >= 0 && target > 0) {
		right = findNum(0, right, target);
		for (int i = 0; i < list[right].count; i++) {
			if (target - list[right].money >= 0) {
				target -= list[right].money;
				count++;
			}
			else
				break;
		}
		right--;
	}
	if (count == 0)
		printf("Impossiable!");
	else
		printf("count=%d", count);
	free(list);
}

int main() {
	init();
	match();
	return 0;
}

原文地址：http://www.cnblogs.com/cony1/p/16875489.html