算法题之装空调
291 / 3 / 创建于 3年前 /
Dennis_Ritchie 的个人博客
前言
昨天看到一个算法题，挺有意思的，大家分享下，这道题被定义为困难。
题目
学校要装空调了！！！
9102年，学校终于要装空调了，学生们都欢呼雀跃的期待着学校赶紧把空调装好。但是学校招过来的安装空调的人却不够了，同一时间只能安装一个空调，这引起了大家的不满。大家都希望学校能够先装自己宿舍，如果装的太晚就要抗议。
假设学校共有 n 栋宿舍楼，每栋宿舍楼有 m 间宿舍，每间宿舍都有大小不同的忍受度。学校装空调时，只能把同一栋楼的空调安装完毕后才能安装其他宿舍楼的空调。
作为校长精明能干的助手，校长希望你能够安排好学校安装空调的顺序，让抗议的宿舍数最少。（增添人手的钱都用来买空调了，别想在招人了）
入参有三个，第一个输入一个整数n，表示n栋宿舍楼；
第二个输入一个整数m，表示每栋楼有m间宿舍；
接下来输入一个n*m的矩阵，表示每栋宿舍楼的每间宿舍的忍受度f(ij)。
(1 <= n <=20 ,1<=m <=1000,1<=f(ij)<=n *m)。
注释：忍受度：如果某个宿舍宿舍是所有宿舍（包含其他宿舍楼的宿舍）中第 x 个装空调的(x > f_{ij}) , 那么这个宿舍就要去抗议。
输出最少的抗议的宿舍数。
示例1
输入：
3
3
[[3,1,2],[6,5,8],[7,3,4]]
输出：
2注意
安装空调的顺序依次为：
(1,2)，(1,3)，(1,1)
(2,2)，(2,1)，(2,3)
(3,1)，(3,2)，(3,3)实现代码
package solution70;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Solution {
private int minCount = Integer.MAX_VALUE;
private int position = 0;//from 1
private int currentCount = 0;
private List<Floor> floors;
private int n;
private int m;
private List<Room> orderedRooms = new ArrayList<>();
public int solution(int n, int m, int[][] f) {
initData(n, m, f);
this.start();
return minCount;
}
private void initData(int n, int m, int[][] f) {
this.n = n;
this.m = m;
int i = 0;
int j;
ArrayList<Floor> floors = new ArrayList<>();
for (; i < n; i++) {
ArrayList<Room> rooms = new ArrayList<>();
for (j = 0; j < m; j++) {
rooms.add(new Room(false, f[i][j], i + 1, j + 1));
}
sortRooms(rooms);
Floor floor = new Floor(false, rooms);
floors.add(floor);
}
this.floors = floors;
}
private void sortRooms(List<Room> rooms) {
rooms.sort(new Comparator<Room>() {
@Override
public int compare(Room o1, Room o2) {
return o1.getEndurance() - o2.getEndurance();
}
});
}
private void start() {
boolean allChecked = true;
FloorResult result;
for (Floor f :
floors) {
if (!f.isChecked()) {
f.setChecked(true);
result = calculateFloor(f);
allChecked = false;
position -= result.getIterateCount();
currentCount -= result.getCount();
f.setChecked(false);
}
}
//the last floor
if (allChecked) {
if (currentCount < minCount) {
minCount = currentCount;
printRoom();
}
System.out.println("min:" + minCount + " and now:" + currentCount);
}
}
private void printRoom() {
for (Floor f :
this.floors) {
System.out.println("-----------------");
for (Room m :
f.getRooms()) {
System.out.println("(" + m.getPosition() + "," + m.getEndurance() + ")");
}
System.out.println("-----------------");
}
}
private FloorResult calculateFloor(Floor floor) {
boolean afterShouldProtest = false;
FloorResult result = new FloorResult();
int reservedPosition;
int reservedCount;
boolean isFound = false;
// List<Room> cur = new ArrayList<>();
for (Room r :
floor.getRooms()) {
if (!r.isChecked()) {
result.incrIterateCount();
position++;
r.setChecked(true);
isFound = false;
//cur.add(r);
if (r.getEndurance() < position) {
for (Room m :
floor.getRooms()) {
/* boolean checked = m.isChecked();
m.setChecked(true);*/
if (!m.isChecked() && m.getEndurance() >= position) {
//skip
m.setChecked(true);
isFound = true;
m.setPosition(position);
break;
}
}
r.setPosition(0);
currentCount++;
result.incrCount();
if (!afterShouldProtest) {
afterShouldProtest = true;
}
if (currentCount >= minCount) {
//restore
for (Room k :
floor.getRooms()) {
k.setChecked(false);
}
return result;
}
} else {
r.setPosition(position);
}
}
}
//restore
for (Room r :
floor.getRooms()) {
r.setChecked(false);
}
reservedPosition = position;//reserve
reservedCount = currentCount;
//next floor
start();
position = reservedPosition;
currentCount = reservedCount;
return result;
}
private static class Floor {
private boolean isChecked;
private List<Room> rooms;
public Floor(boolean isChecked, List<Room> rooms) {
this.isChecked = isChecked;
this.rooms = rooms;
}
public boolean isChecked() {
return isChecked;
}
public void setChecked(boolean checked) {
isChecked = checked;
}
public List<Room> getRooms() {
return rooms;
}
public void setRooms(List<Room> rooms) {
this.rooms = rooms;
}
public void addRoom(Room room) {
rooms.add(room);
}
}
private static class Room {
private boolean isChecked;
private int endurance;
private int x;
private int y;
private int position;
public Room(boolean isChecked, int endurance, int x, int y) {
this.isChecked = isChecked;
this.endurance = endurance;
this.x = x;
this.y = y;
}
public boolean isChecked() {
return isChecked;
}
public void setChecked(boolean checked) {
isChecked = checked;
}
public int getEndurance() {
return endurance;
}
public void setEndurance(int endurance) {
this.endurance = endurance;
}
@Override
public String toString() {
return "Room{" +
"isChecked=" + isChecked +
", endurance=" + endurance +
", x=" + x +
", y=" + y +
'}';
}
public int getPosition() {
return position;
}
public void setPosition(int position) {
this.position = position;
}
}
private static class FloorResult {
private int iterateCount;
private int count;
public FloorResult() {
}
public FloorResult(int iterateCount, int count) {
this.iterateCount = iterateCount;
this.count = count;
}
public int getIterateCount() {
return iterateCount;
}
public void setIterateCount(int iterateCount) {
this.iterateCount = iterateCount;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public void incrIterateCount() {
iterateCount++;
}
public void incrCount() {
count++;
}
}
}
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：