HouseParty(赛前模拟题)

Problem Statement
????
We are building a rectangular house using manufactured sections for the walls. Each section is 4 feet long. There are three types of sections: window sections, door sections, and regular sections. We have a fixed assortment of these sections, and want to design the house to have a maximum area, subject to the following rules:
1) A house side must contain no more than one door.
2) The house must have at least one door.
3) A door section may not be at the end of a wall.
4) Each window section must be adjacent to two regular sections, one on each side of it in its wall.
Create a class HouseParty that contains a method maxArea that is given numReg, numWin, and numDoor (the available quantity of each type of section) and that returns the maximum area of a house built from those sections. You are not required to use all the sections. If no house can be built your method should return 0.
Definition
????
Class:
HouseParty
Method:
maxArea
Parameters:
int, int, int
Returns:
int
Method signature:
int maxArea(int numReg, int numWin, int numDoor)
(be sure your method is public)
????

Constraints
-
numReg, numWin, and numDoor will each be between 0 and 50 inclusive.
Examples
0)

????
8
0
0
Returns: 0
No house can be built since you have no door sections.
1)

????
8
0
1
Returns: 48
One way is to use 3 regular sections for the north wall, one regular section for the east wall and one for the west wall, and to use a door section between 2 regular sections for the south wall. This gives a house that is 12' x 4'. Below is a picture (with door and window sections shown as D and W, and regular sections shown as - or | )

    ---
   |   |
    -D-
2)

????
9
8
2
Returns: 144
One design is:
    -D-
   |   |
   D   W
   |   |
    -W-
3)

????
6
23
13
Returns: 48
We are very short of regular sections; one design is:
    -
   | |
   D W
   | |
    -

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-08-16 09:28 emu 阅读(1949) 评论(11) 编辑收藏所属分类: google编程大赛模拟题及入围赛真题

# emu 第一次的解法 2005-08-16 09:34 emu

穷举法。其中用了3进制代替多重循环遍历。时间复杂度超过题目要求，失败！

import java.util.*;

public class HouseParty {
public static void main(String[] args) {
HouseParty hp = new HouseParty();
//hp.maxArea(3,0,0);
long startBy = System.currentTimeMillis();
/*
System.out.println(hp.maxArea(7, 0, 1));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println(hp.maxArea(9, 8, 2));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println(hp.maxArea(6, 23, 13));
System.out.println("biggest room:" + hp.biggestRoom);
*/
System.out.println("(16, 0, 4):"+hp.maxArea(16, 0, 4));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println("(16, 2, 1):"+hp.maxArea(16, 2, 1));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println("(16, 4, 4):"+hp.maxArea(16, 4, 4));
System.out.println("biggest room:" + hp.biggestRoom);
System.out.println("time used:" + (System.currentTimeMillis() - startBy));
}

private int numReg, numWin, numDoor;
private int REG = 0, WIN = 1, DOOR = 2;
private Room biggestRoom = null;
public int maxArea(int numReg, int numWin, int numDoor) {
if (numDoor == 0)
return 0;
if (numReg < 4)
return 0;
if (numDoor > 4)
numDoor = 4;
if (numWin > numReg / 2)
numWin = numReg / 2;
this.numReg = numReg;
this.numWin = numWin;
this.numDoor = numDoor;
ArrayList possibleWalls = getPossibleWals(numReg / 2 , numWin,1);
int result = getMaxArea(possibleWalls);
return result * 16;
}

private ArrayList getPossibleWals(int numReg, int numWin, int numDoor) {
ArrayList result = new ArrayList();
if (numWin > numReg / 2 - 1)
numWin = numReg / 2 - 1;
if (numDoor > 1)
numDoor = 1;
int wallMaxLength = numReg + numWin + numDoor;
for (int wallLength = 1; wallLength < wallMaxLength; wallLength++) {
for (int i = 0, n = new Double(Math.pow(3, wallLength)).intValue();
i < n; i++) { //这样穷举的效率很低，应用递归检查
Wall wall = new Wall();
wall.wall = new int[wallLength];
int tmp = i;
for (int j = 0; j < wallLength; j++) {
wall.wall[j] = tmp % 3;
tmp = tmp / 3;
}
if (wall.checkRule()) {
result.add(wall);
}
}
}
return result;
}

private int getMaxArea(ArrayList possibleWalls) {
int wallCount = possibleWalls.size();
int result = 0;
for (int iWallEast = 0; iWallEast < wallCount; iWallEast++) {
Wall east = (Wall) possibleWalls.get(iWallEast);
for (int iWallWest = 0; iWallWest < wallCount; iWallWest++) {
Wall west = (Wall) possibleWalls.get(iWallWest);
if (east.wall.length != west.wall.length)
continue;
if (east.wall.length != west.wall.length)
continue;
if (east.getRegCount() + west.getRegCount() > numReg)
continue;
if (east.getWinCount() + west.getWinCount() > numWin)
continue;
if (east.getDoorCount() + west.getDoorCount() > numDoor)
continue;
for (int iWallSouth = 0; iWallSouth < wallCount; iWallSouth++) {
Wall south = (Wall) possibleWalls.get(iWallSouth);
if (east.getRegCount() + west.getRegCount() +
south.getRegCount() > numReg)
continue;
if (east.getWinCount() + west.getWinCount() +
south.getWinCount() > numWin)
continue;
if (east.getDoorCount() + west.getDoorCount() +
south.getDoorCount() > numDoor)
continue;
for (int iWallNorth = 0; iWallNorth < wallCount; iWallNorth++) {
Wall north = (Wall) possibleWalls.get(iWallNorth);
if (south.wall.length != north.wall.length)
continue;
if (east.getRegCount() + west.getRegCount() +
south.getRegCount() + north.getRegCount() > numReg)
continue;
if (east.getWinCount() + west.getWinCount() +
south.getWinCount() + north.getWinCount() > numWin)
continue;
if (east.getDoorCount() + west.getDoorCount() +
south.getDoorCount() + north.getDoorCount() >
numDoor)
continue;
if (east.getDoorCount() + west.getDoorCount() +
south.getDoorCount() + north.getDoorCount() < 1)
continue;
Room room = new Room(east, south, west, north);
if (room.getArea() > result) {
result = room.getArea();
biggestRoom = room;
}
}
}
}
}
return result;
}

private class Wall {
public int[] wall;
public int[] combinationCount;
public int getRegCount() {
return combinationCount[REG];
}

public int getWinCount() {
return combinationCount[WIN];
}

public int getDoorCount() {
return combinationCount[DOOR];
}

public String toString() {
char[] tmp = new char[] {'R', 'W', 'D'};
String result = "";
for (int i = 0; i < wall.length; i++)
result += tmp[wall[ i ]];
return result;

}

public boolean checkRule(){
this.combinationCount = new int[3];
if (wall[0] == DOOR)
return false;
if (wall[wall.length - 1] == DOOR)
return false;
if (wall[0] == WIN)
return false;
if (wall[wall.length - 1] == WIN)
return false;
for (int i = 0, n = wall.length; i < n; i++)
if (wall[ i ] == WIN && (wall[i - 1] != REG || wall[i + 1] != REG))
return false;
else
combinationCount[wall[ i ]]++;
if (getRegCount() < 1)
return false;
if (getRegCount() > numReg)
return false;
if (getWinCount() > numWin)
return false;
if (getDoorCount() > numDoor)
return false;
if (getDoorCount() > 1)
return false;
return true;
}
}

private class Room {
Wall east, south, west, north;
public Room(Wall east, Wall south, Wall west, Wall north) {
this.east = east;
this.south = south;
this.west = west;
this.north = north;
}

public int getArea() {
if (east.wall.length != west.wall.length)
return 0;
if (south.wall.length != north.wall.length)
return 0;
if (east.getRegCount() + west.getRegCount() + south.getRegCount() +
north.getRegCount() > numReg)
return 0;
if (east.getWinCount() + west.getWinCount() + south.getWinCount() +
north.getWinCount() > numWin)
return 0;
if (east.getDoorCount() + west.getDoorCount() + south.getDoorCount() +
north.getDoorCount() > numDoor)
return 0;
if (east.getDoorCount() + west.getDoorCount() + south.getDoorCount() +
north.getDoorCount() < 1)
return 0;
return east.wall.length * south.wall.length;

}

public String toString() {
return "east:" + east + "\tsouth:" + south + "\twest:" + west +
"\tnorth:" + north;
}
}
}

回复更多评论

# 秋水无恨的javascript版答案，第三次修正版。 2005-08-16 09:36 emu

# emu第二次的解法 2005-08-16 09:37 emu

这次时间复杂度降到了o〔n)，结果也正确了，从代码可以看得清思路。

public class HouseParty {
    public static void main(String[] args) {
        HouseParty hp = new HouseParty();
        long startBy = System.currentTimeMillis();
        System.out.println("(50,50,50):" + hp.maxArea(50, 50, 50));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(8, 0, 0):" + hp.maxArea(8, 0, 0));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(8, 1, 1):" + hp.maxArea(8, 1, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(7, 0, 1):" + hp.maxArea(7, 0, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 8, 2):" + hp.maxArea(9, 8, 2));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(6, 23, 13):" + hp.maxArea(6, 23, 13));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(16, 0, 4):" + hp.maxArea(16, 0, 4));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(16, 2, 1):" + hp.maxArea(16, 2, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(16, 4, 4):" + hp.maxArea(16, 4, 4));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 0, 3):" + hp.maxArea(9, 0, 3));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(8, 0, 4):" + hp.maxArea(8, 0, 4));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 1, 2):" + hp.maxArea(9, 1, 2));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("(9, 2, 1):" + hp.maxArea(9, 2, 1));
        System.out.println("biggest room:" + hp.biggestRoom);
        System.out.println("time used:" + (System.currentTimeMillis() - startBy));

    }

    public Room biggestRoom;
    public int maxArea(int numReg, int numWin, int numDoor) {
        biggestRoom = null;
        if (numReg < 6)
            return 0;
        if (numDoor < 1)
            return 0;
        if (numReg + numWin + numDoor < 8)
            return 0;
        Room initialRoom = null;
        if (numDoor > 1) {
            initialRoom = new Room("RDR", "R", "RDR", "R");
            numReg -= 6;
            numDoor -= 2;
        } else if (numWin > 0) {
            initialRoom = new Room("RDR", "R", "RWR", "R");
            numReg -= 6;
            numDoor -= 1;
            numWin -= 1;
        } else {
            initialRoom = new Room("RDR", "R", "RRR", "R");
            numReg -= 7;
            numDoor -= 1;
        }

        if (numDoor >= 2 && numReg >= 2) {
            initialRoom.appendWalls("DR", "DR");
            numDoor -= 2;
            numReg -= 2;
        } else if (numDoor >= 1) {
            if (numWin >= 1 && numReg >= 2) {
                initialRoom.appendWalls("DR", "WR");
                numWin -= 1;
                numDoor -= 1;
                numReg -= 2;
            } else if (numReg >= 3) {
                initialRoom.appendWalls("DR", "RR");
                numDoor -= 1;
                numReg -= 3;
            }
        }

        while (numWin >= 2 && numReg >= 2) {
            initialRoom.appendWalls("WR", "WR");
            numWin -= 2;
            numReg -= 2;
        }
        if (numWin >= 1 && numReg >= 3) {
            initialRoom.appendWalls("WR", "RR");
            numWin -= 1;
            numReg -= 3;
        } while (numReg >= 2) {
            initialRoom.appendWalls("R", "R");
            numReg -= 2;
        }
        biggestRoom = initialRoom;
        return initialRoom.getArea() * 16;
    }

    private class Room {
        StringBuffer east, south, west, north;
        public Room(String east, String south, String west, String north) {
            this.east = new StringBuffer(east);
            this.south = new StringBuffer(south);
            this.west = new StringBuffer(west);
            this.north = new StringBuffer(north);
        }

        public int getArea() {
            return east.length() * south.length();
        }

        public String toString() {
            return "east:" + east + "\tsouth:" + south + "\twest:" + west +
                    "\tnorth:" + north;
        }

        public void appendWalls(String w1, String w2) {
            if (east.length() < south.length()) {
                east.append(w1);
                west.append(w2);
            } else {
                south.append(w1);
                north.append(w2);
            }
        }
    }
}

  回复   更多评论

# emu的最终解法 2005-08-16 09:39 emu

赶上秋水无恨第一次的解法了，时间复杂度o(1)。

public class HouseParty {
public static void main(String[] args) {
HouseParty hp = new HouseParty();
//hp.maxArea(3,0,0);
long startBy = System.currentTimeMillis();
System.out.println("(8, 0, 0):"+hp.maxArea(8, 0, 0));
System.out.println("(7, 0, 1):"+hp.maxArea(7, 0, 1));
System.out.println("(9, 8, 2):"+hp.maxArea(9, 8, 2));
System.out.println("(6, 23, 13):"+hp.maxArea(6, 23, 13));
System.out.println("(16, 0, 4):"+hp.maxArea(16, 0, 4));
System.out.println("(16, 2, 1):"+hp.maxArea(16, 2, 1));
System.out.println("(16, 4, 4):"+hp.maxArea(16, 4, 4));
System.out.println("(1024, 324, 4):"+hp.maxArea(1024, 324, 4));
System.out.println("(9, 0, 3):"+hp.maxArea(9, 0, 3));
System.out.println("time used:" + (System.currentTimeMillis() - startBy));
}
public int maxArea(int numReg, int numWin, int numDoor) {
int width = 0;
int length = 0;
if (numDoor>4) numDoor =4;
if (numReg<6) return 0;
if (numDoor<1) return 0;
if (numReg+numWin+numDoor<8) return 0;
if (numDoor>1) {
width = 1;
length = 3;
numReg -= 6;
numDoor -= 2;
}else if (numWin>1){
width = 1;
length = 3;
numReg -= 6;
numDoor -= 1;
numWin -= 1;
}else{
width = 1;
length = 3;
numReg -= 7;
numDoor -= 1;
}
if (numDoor >=2 && numReg>=2){
if (width<length) width += 2; else length += 2;
numDoor -= 2;
numReg -= 2;
}

if (numWin >=2 && numReg>=2){
int n = Math.min(numWin,numReg)/2;
int m = n/2; n -= m;
if (width<length) {
width += n*2;
length += m*2;
} else{
width += m*2;
length += n*2;
}
numWin -= 2*(n+m);
numReg -= 2*(n+m);
}

if (numDoor >=1 && numWin >=1 && numReg>=2){
if (width<length) width += 2; else length += 2;
numWin -= 1;
numDoor -= 1;
numReg -= 2;
}
if ((numDoor >=1 || numWin >=1) && numReg>=3){
if (width<length) width += 2; else length += 2;
numReg -= 3;
}
if (numReg>=2){
int n = numReg/2;
int m = n/2; n -= m;
if (width<length) {
width += n;
length += m;
} else{
width += m;
length += n;
}
}
return width*length*16;
}
}

回复更多评论

# re: HouseParty 2005-08-23 18:18 emu

居然系统测试失败
Failed system test 10 on the 375-point problem with args: [8, 1, 1]
EXPECTED: 96
RECEIVED: 48

Failed system test 5 on the 375-point problem with args: [50, 50, 50]
EXPECTED: 9200
RECEIVED: 3360 回复更多评论

# re: HouseParty(赛前模拟题) 2005-12-10 17:33 小飞侠

public class test {
//初始化房间,扣除使用的原材料,返回初始化房间数组
public static StringBuffer[] initRoom(int bres[]) {
StringBuffer[] myroom = new StringBuffer[4];

//数组内元素的初始化
myroom[0] = new StringBuffer();
myroom[1] = new StringBuffer();
myroom[2] = new StringBuffer();
myroom[3] = new StringBuffer();

if (bres[2] == 4) {
if (bres[0] >= 8) {
//初始化4个门的room
myroom[0].append("-D-");
myroom[1].append("-D-");
myroom[2].append("-D-");
myroom[3].append("-D-");
bres[0] -= 8;
bres[2] -= 4;
return myroom;
}
}

if (bres[2] >= 3) {
if (bres[1] >= 1) {
if (bres[0] >= 8) {
//初始化3个门的room
myroom[0].append("-D-");
myroom[1].append("-D-");
myroom[2].append("-D-");
myroom[3].append("-W-");
bres[0] -= 8;
bres[1] -= 1;
bres[2] -= 3;
return myroom;
}
} else {
if (bres[0] >= 9) {
myroom[0].append("-D-");
myroom[1].append("-D-");
myroom[2].append("-D-");
myroom[3].append("---");
bres[0] -= 9;
bres[2] -= 3;
return myroom;
}
}
}

if (bres[2] >= 2) {
if (bres[0] >= 6) {
//初始化4个门的room
myroom[0].append("-D-");
myroom[1].append("-");
myroom[2].append("-D-");
myroom[3].append("-");
bres[0] -= 6;
bres[2] -= 2;
return myroom;
}
}

if (bres[2] >= 1) {
if (bres[1] >= 1) {
if (bres[0] >= 6) {
//初始化3个门的room
myroom[0].append("-D-");
myroom[1].append("-");
myroom[2].append("-W-");
myroom[3].append("-");
bres[0] -= 6;
bres[1] -= 1;
bres[2] -= 1;
return myroom;
}
} else {
if (bres[0] >= 7) {
myroom[0].append("-D-");
myroom[1].append("-");
myroom[2].append("---");
myroom[3].append("-");
bres[0] -= 7;
bres[2] -= 1;
return myroom;
}
}
}

return myroom;
}

-->>未完待续回复更多评论

# re: HouseParty(赛前模拟题) 2005-12-10 17:34 小飞侠

//--接上
public static int getArea(int x, int y) {
return x * y;
}

public static int maxArea(int wall, int window, int door) {
int[] res = new int[3];
StringBuffer[] room;
int i, j;

System.out.println("总材料, wall="+wall+";window"+window+";door"+door);

if (door > 4) door = 4;
res[0] = wall;
res[1] = window;
res[2] = door;

if (door == 0) {
System.out.println("Room can not be inited");
return 0;
}

//第一步,初始化房间,原则尽可能多的使用门.
room = initRoom(res);

if (room[0].length() == 0) {
System.out.println("Room can not be inited");
return 0;
}

//测试初始化情况,输出图形,和输出剩下的元素.
System.out.println("初始化房子:");
for(i=0; i < 4; i++) {
System.out.println(room[i]);
}
System.out.println("剩余的材料:");
System.out.println("wall="+res[0]);
System.out.println("window="+res[1]);
System.out.println("door="+res[2]);

//第二步,初始化成功后,开始有条件约束的添加窗和门.
if (res[0] < 2 ) {
return getArea(room[0].length(), room[1].length());
}

//获取当前条件下,能使用的窗的总数,
if (res[1] > 0) {
if ( res[1] % 2 == 0 ) {
//如果窗户是偶数
if (res[0] < res[1]) {
res[1] = res[0];
}
} else {
//如果窗户是奇数
if (res[0] < res[1] + 2) {
res[1] = res[0] - 2;
}
}
}

//获取了能使用的窗总数后,判断现在的窗的奇偶.
j = room[0].length() >= room[1].length() ? 1 : 0;
if (res[1] % 2 == 0){
while(res[1] > 0 && res[0] >= 2) {
room[j].append("W-");
room[j+2].append("W-");
res[0] -= 2;
res[1] -= 2;
j = 1 - j;
}
} else {
while(res[1] > 1 && res[0] >= 2) {
room[j].append("W-");
room[j+2].append("W-");
res[0] -= 2;
res[1] -= 2;
j = 1 - j;
}
//余一
if (res[0] >= 3) {
room[j].append("W-");
room[j+2].append("--");
res[0] -= 3;
res[1] -= 1;
j = 1 - j;
}
}

//最后,如果剩余的墙,按照偶数个添加.
if (res[0] % 2 == 0){
while(res[0] > 0) {
room[j].append("-");
room[j+2].append("-");
res[0] -= 2;
j = 1 - j;
}
} else {
while(res[0] > 1) {
room[j].append("-");
room[j+2].append("-");
res[0] -= 2;
j = 1 - j;
}
//余一, 不处理

}

//测试初始化情况,输出图形,和输出剩下的元素.
for(i=0; i < 4; i++) {
System.out.println(room[i]);
}
System.out.println("剩余的材料:");
System.out.println("wall="+res[0]);
System.out.println("window="+res[1]);
System.out.println("door="+res[2]);

return getArea(room[0].length(), room[1].length());
}

public static void main(String args[]) {
int wall, door, window, mymax;

wall = 6;
window = 23;
door = 13;
mymax = maxArea(wall, window, door);

System.out.println("最大面积="+mymax);
}
}

回复更多评论

# re: HouseParty(赛前模拟题) 2005-12-10 17:48 小飞侠

以上仅仅是按照自己的想法,做了一个大概的程序流程,尚未进行任何优化,但是思想很简单, 首先遵循三个原则, 门最大使用度,窗最大使用度, 尽可能接近正方形. 然后,在约束条件和三大原则的指导下,先初始化房子(即可能的最小面积),之后,根据剩下的原始材料进行添窗加墙. 最后剩下的就是无法使用的材料.

其实,这个方法还是很麻烦,如果不需要考虑房子怎么建造,而仅仅是需要一个最大面积,还有有更简单的方法, 思想就是,只要满足约束条件,剔除多余的原材料,剩下的都是等单元,将剩下的所有,管他是门是窗是墙,加起来,求一个尽可能正方的结果,完.

回复更多评论

# re: HouseParty(赛前模拟题) 2005-12-19 14:41 longn_qi

// 问题分析：
// （1）围一间房的面积一定大于围多间房，所以只考虑围一间房。
// （2）只计算最优结果，不需要给出方案。
// （3）门必须有1，超过4个的剩余不用。门窗合在一起算，不区分。
// （4）墙板必须多于6，至少超过门窗4个，当恰好超过4个时，墙板必须为偶数，且房屋的长宽均为奇数。
// （5）使用的材料总数必须为偶数。
// （6）房屋的长和宽越接近面积越大。
// （7）因为至少有一扇门，所以房屋的长和宽至少有一个大于2。

int maxArea(int numReg, int numWin, int numDoor)
{
int used = 0;
int width, height;

if( numDoor < 1 || numReg < 6 || numWin < 0 )
{
return 0;
}

if( numDoor > 4 )
{
numDoor = 4;
}

if( numReg > numWin + numDoor + 4 )
{
used = ( ( numReg + numWin + numDoor ) >> 1 ) << 1;
width = used / 4;
}
else
{
used = ( ( numReg * 2 - 4 ) >> 2 ) << 2;
width = used / 8 * 2 + 1;
}

height = used / 2 - width;
if( height < 3 )
{
height = 3;
width = used / 2 - height;
}

return width * height * 16;
} 回复更多评论

# re: HouseParty(赛前模拟题) 2008-07-10 18:35 J.A.M

由于没有测试环境，仅对题目中的情况进行测试。
代码如下：
#include <iostream>
using namespace std;

int maxArea(int aRegular, int aWindow, int aDoor)
{
if (aDoor < 1)
return 0;
if (aRegular < 6)
return 0;
if (aDoor > 4)
aDoor = 4;
int maxLen = aRegular + min(aDoor + aWindow, aRegular - 4);
maxLen = maxLen / 2;
int h = max(maxLen / 2, 3);
int w = maxLen - h;
if ((w-3)%2 == 1)
w = w - 1;
return (h* w) * 16;
};

int main(int argc, char* argv[])
{
cout<<maxArea(8,0,0)<<endl;
cout<<maxArea(8,0,1)<<endl;
cout<<maxArea(9,8,2)<<endl;
cout<<maxArea(6,23,13)<<endl;
cin.get();
return 0;
}
回复更多评论

# re: HouseParty(赛前模拟题) 2008-07-10 19:06 J.A.M

不严谨，少判断了一边
int maxArea(int aRegular, int aWindow, int aDoor)
{
if (aDoor < 1)
return 0;
if (aRegular < 6)
return 0;
if (aDoor > 4)
aDoor = 4;
int maxLen = aRegular + min(aDoor + aWindow, aRegular - 4);
maxLen = maxLen / 2;
int h = max(maxLen / 2, 3);
if ((h-3)%2 == 1)
h = h - 1;
int w = maxLen - h;
if ((w-3)%2 == 1)
w = w - 1;
return (h* w) * 16;
};
回复更多评论

新用户注册刷新评论列表


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理
相关文章: 没忍住手痒做了一道题，结果还没作对。差点被燕潘考倒了 1000分模拟题CraneWork 500分模拟题 MaximalPalindromeSubstrings 250分模拟题 SalesRouting SecretSum (code jam china round2 500分真题) FactorialSystem (code jam china round2 300分真题) RecurringNumbers (code jam china 1000分真题) google中国编程挑战赛入围赛真题 -- HardDuplicateRemover(1000分) google中国编程挑战赛入围赛真题 -- BlockStructure(500分)

emu in blogjava

公告

常用链接

留言簿(92)

随笔分类(20)

随笔档案(171)

文章分类(89)

文章档案(103)

相册

收藏夹(46)

友情连接

收藏

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

评论