Code03-贪心算法

ZOJ 2109

// 一个显示答案错误的代码
package ZOJ;

import java.util.Arrays;
import java.util.Scanner;

class Node {
	int f, j;
	double rate;

	public Node(int f, int j) {
		this.f = f;
		this.j = j;
		this.rate = j * 1.0 / f; // 计算 rate
	}
}

public class ZOJ_2109_02 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int m = 0;
		int n = 0;
		while (m != -1 && n != -1) {
			m = scanner.nextInt();
			n = scanner.nextInt();

			if (m == -1 && n == -1)
				break;

			Node[] rooms = new Node[n];

			for (int i = 0; i < n; i++) {
				int j = scanner.nextInt();
				int f = scanner.nextInt();
				rooms[i] = new Node(f, j);
			}

			// 按照 rate（每单位猫粮的价值）降序排序
			Arrays.sort(rooms, (lhs, rhs) -> Double.compare(rhs.rate, lhs.rate));

			double sum = 0.0;
			for (int i = 0; i < n; i++) {
				if (m == 0)
					break;

				if (m >= rooms[i].f) {
					m -= rooms[i].f;
					sum += rooms[i].j;
				} else {
					sum += rooms[i].rate * m;
					m = 0;
					break;
				}
			}

			System.out.printf("%.3f\n", sum);
		}

		scanner.close();
	}
}

思路：

贪心算法的标准模板，就是过不了。。。

• 定义类：包括每个物品的空间、价值和单位价值，构造函数；

• 定义一个自定义类类型的数组，该题目中每个房间相当于一个物品;

• 按照单位价值降序排序：

  Arrays.sort(rooms,(lhs,rhs) -> Double.compare(rhs.rate,lhs.rate));
  

• 比较当前容量和下一个物品空间：

  • 若当前剩余容量足够容纳下个物品的全部：直接将全部装入；
  • 若不足，则将剩余容量乘以物品单位价值

注意事项：

错误的原因写在这，大坑预定

---

HDU 6180

内存超出代码：使用数组

package HDU;

import java.util.Scanner;

class schedule {
	int start;
	int end;

	public schedule(int start, int end) {
		this.start = start;
		this.end = end;
	}
}

public class HDU_6180 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int epochs = scanner.nextInt();
		int machineCnt = 0;
		for (int epoch = 0; epoch < epochs; epoch++) {
			machineCnt = 0;
			int cnt = scanner.nextInt();
			schedule[][] m = new schedule[cnt][cnt];
			int[] inCnt = new int[cnt]; // 表示每个机器内已经安排的日程数目
			for (int i = 0; i < cnt; i++) {
				boolean add = false;
				int startRe = scanner.nextInt();
				int endRe = scanner.nextInt(); // 临时记录日程时间
				if (i == 0) {
					m[0][0] = new schedule(startRe, endRe);
					machineCnt++;
					inCnt[0]++;
					add = true;
				} else {
					for (int j = 0; j < machineCnt; j++) {
						if (startRe >= m[j][inCnt[j] - 1].end) {
							m[j][inCnt[j]] = new schedule(startRe, endRe);
							inCnt[j]++;
							add = true;
							break;
						}
					}
					if (!add) {
						m[machineCnt][0] = new schedule(startRe, endRe);
						inCnt[machineCnt]++;
						machineCnt++;
					}
				}
			}

			int totalT = 0;

			for (int i = 0; i < machineCnt; i++) {
				totalT = totalT + m[i][inCnt[i] - 1].end - m[i][0].start;
			}
			System.out.println(machineCnt + " " + totalT);

		}
	}
}

---