亚洲影院天堂中文av色,国产精品推荐精品,久久亚洲精品一区二区

NewStation(入圍賽750分真題)

Problem Statement
????
You are given a String[], grid, representing a city where each character in grid is a single city block. Each block will contain a digit representing the relative population on that block. For example, a block containing the digit '6' will contain three times as many people as a block containing the digit '2'. You are also given a String[], stations, containing the locations of all the fire stations within the city. Each element of stations is formatted as "r c" (quotes for clarity only), where r and c represent the row and column, respectively, of the block on which a fire station is located. Character j of element i of grid represents the block at row i, column j. All indices are 0-based.

The city has received enough funds to build one additional fire station, and the mayor has decided that it is most important to minimize the average distance between a person and the closest fire station to that person. The metric used to determine the distance between two locations in the city is the Manhattan distance between the two blocks on which the locations are situated. The Manhattan distance between two blocks (r1, c1) and (r2, c2) is |r1-r2|+|c1-c2| (the vertical bars represent absolute value). Determine the block on which the new station should be built and return its row and column formatted as "r c" (quotes for clarity only). The return String should contain no extra leading zeros. If multiple blocks are equally optimal, return the one with the lowest row, and if multiple optimal blocks have the same lowest row, return the one among them with the lowest column. If adding an additional fire station would not reduce the average distance between a person and the closest fire station to that person, return the empty String ("").
Definition
????
Class:
NewStation
Method:
location
Parameters:
String[], String[]
Returns:
String
Method signature:
String location(String[] grid, String[] stations)
(be sure your method is public)
????

Constraints
-
grid will contain between 1 and 20 elements, inclusive.
-
Each element of grid will contain between 1 and 20 characters, inclusive.
-
Each element of grid will contain exactly the same number of characters.
-
Each element of grid will contain only digits ('0'-'9').
-
At least one character in grid will be non-zero.
-
stations will contain between 1 and 10 elements, inclusive.
-
Each element of stations will be formatted as "r c" (quotes for clarity only), where r and c are each integers between 0 and 19, inclusive, with no leading zeros.
-
Each element of stations will represent a location within the boundaries of grid.
Examples
0)

????
{"111",
"111",
"111"}
{"1 1"}
Returns: "0 1"
There's an existing station at (1, 1) and each block contains exactly the same number of people. Placing a new station at either (0, 1), (1, 0), (1, 2), or (2, 1) would minimize the average distance. (0, 1) is chosen since it has the lowest row. Adding the new station reduces the average distance from approximately 1.33 to 1.0. The distance from each block to the nearest station becomes:
101
101
212
1)

????
{"111",
"111",
"111"}
{"0 0", "0 1", "0 2",
"1 0", "1 1", "1 2",
"2 0", "2 1", "2 2"}
Returns: ""
There's a fire station on every block, so adding a new station would not reduce the average distance.
2)

????
{"2312",
"0233"}
{"1 3"}
Returns: "0 1"
Placing a fire station at (0, 1) would make the average distance 0.625.
3)

????
{"2312",
"0233"}
{"1 1", "1 1"}
Returns: "0 3"

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-23 16:37 emu 閱讀(1685) 評論(4) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

public class NewStation {
    public static void main(String[] args) {
        NewStation ns = new NewStation(); ;
        String[] grid = {"2312",
"0233"};
        String[] stations = {"1 1", "1 1"};
        System.out.println(ns.location(grid, stations));
    }

    public String location(String[] grid, String[] stations) {
        int[][] iGrid = new int[grid.length][grid[0].length()];
        for (int i = 0; i < grid.length; i++) {
            String s = grid[i];
            for (int j = 0; j < s.length(); j++) {
                iGrid[i][j] = s.charAt(j) - 48;
            }
        }
        boolean[][] iStations = new boolean[iGrid.length][iGrid[0].length];
        for (int i = 0; i < stations.length; i++) {
            String[] s = stations[i].split(" ");
            iStations[Integer.parseInt(s[0], 10)][Integer.parseInt(s[1], 10)] = true;
        }
        int minDistanceCount = count(iGrid, iStations);
        String result = "";
        for (int x = 0; x < iGrid.length; x++)
            for (int y = 0; y < iGrid[0].length; y++) {
                int c = count(iGrid, iStations, x, y);
                if (c < minDistanceCount) {
                    result = x + " " + y;
                   minDistanceCount = c;
                }
            }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations) {
        int result = 0;
        for (int i = 0; i < iGrid.length; i++)
            for (int j = 0; j < iGrid[0].length; j++)
                if (!iStations[i][j] && iGrid[i][j] > 0) {
                    int minCount = 99999;
                    for (int x = 0; x < iGrid.length; x++)
                        for (int y = 0; y < iGrid[0].length; y++)
                            if (iStations[x][y] &&
                                (Math.abs(x - i) + Math.abs(y - j) * iGrid[i][j]) <
                                minCount)
                                minCount = Math.abs(x - i) +
                                           Math.abs(y - j) * iGrid[i][j];
                    result += minCount;
                }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations, int x, int y) {
        boolean[][] tmpStations = new boolean[iStations.length][iStations[0].length];
        for (int i=0;i<iStations.length;i++)
            for (int j=0;j<iStations[0].length;j++)
                tmpStations[i][j]=(x==i&&y==j)?(true):(iStations[i][j]);
        return count(iGrid, tmpStations);

    }

}

  回復   更多評論

# re: NewStation(入圍賽750分真題) 2005-08-25 11:01 emu

遺憾的很，我這個答案沒有通過google的系統(tǒng)測試。回復更多評論

# drekar的解法 2005-12-09 12:58 drekar

窮舉：

public class NewStation {

　int MaxRow;
　int MaxCol;
　int NumOfExistedStation;
　int[][] gridMap;
　boolean[][] stationMap;
　int[][] fireStations;

　/**
　 * Find the location for new station.
　 *
　 * @param grid
　 *　　　　　　population for city's each block
　 * @param stations
　 *　　　　　　existed fire stations' coordinate
　 * @return the best location of new station
　 *
　 */
　public String location(String[] grid, String[] stations) {
　　MaxRow = grid.length;
　　MaxCol = grid[0].length();
　　NumOfExistedStation = stations.length;

　　// get grid population map
　　gridMap = new int[MaxRow][MaxCol];
　　for (int i = 0; i < MaxRow; i++)
　　　for (int j = 0; j < MaxCol; j++)
　　　　gridMap[i][j] = grid[i].charAt(j) - '0';

　　// get fire station map
　　stationMap = new boolean[MaxRow][MaxCol];
　　fireStations = new int[NumOfExistedStation + 1][2]; // [][0] for 'row', [][1] for 'column'
　　for (int i = 0; i < NumOfExistedStation; i++) {
　　　String[] temp = stations[i].split(" ");
　　　fireStations[i][0] = Integer.parseInt(temp[0]); // station(#i)'s row
　　　fireStations[i][1] = Integer.parseInt(temp[1]); // station(#i)'s column
　　　stationMap[fireStations[i][0]][fireStations[i][1]] = true; // mark it as a station on the map
　　}

　　int minTotalDistance = Integer.MAX_VALUE;
　　int bestRow = -1;
　　int bestCol = -1;
　　// search for best new station location
　　for (int i = 0; i < MaxRow; i++)
　　　for (int j = 0; j < MaxCol; j++) {
　　　　if (stationMap[i][j])
　　　　　continue;

　　　　// this location has no station, try to set new station here
　　　　fireStations[NumOfExistedStation][0] = i;
　　　　fireStations[NumOfExistedStation][1] = j;

　　　　int newTotalDistance = calculateTotalDistance();
　　　　if (minTotalDistance > newTotalDistance) {
　　　　　// found a better location
　　　　　minTotalDistance = newTotalDistance;
　　　　　bestRow = i;
　　　　　bestCol = j;
　　　　}
　　　}

　　if (bestRow == -1)
　　　return "";
　　return bestRow + " " + bestCol;
　}

　/**
　 * @return total distance if using selected new location
　 */
　public int calculateTotalDistance() {
　　int distance = 0;
　　for (int i = 0; i < MaxRow; i++)
　　　for (int j = 0; j < MaxCol; j++)
　　　　distance += distanceToNearestStation(i, j) * gridMap[i][j];
　　return distance;
　}

　/**
　 * @param row
　 *　　　　　　row of current location
　 * @param col
　 *　　　　　　column of current location
　 * @return distance to the nearest station from location 'row col'
　 */
　public int distanceToNearestStation(int row, int col) {
　　int distance = Integer.MAX_VALUE;
　　for (int i = 0; i < NumOfExistedStation + 1; i++) {
　　　int tempDistance = Math.abs(row - fireStations[i][0])
　　　　　+ Math.abs(col - fireStations[i][1]);
　　　if (distance > tempDistance) {
　　　　distance = tempDistance;
　　　　if (distance == 0)
　　　　　break;
　　　}
　　}
　　return distance;
　}

　/**
　 * 主程序入口
　 *
　 * @param args
　 */
　public static void main(String[] args) {
　　NewStation ns = new NewStation();
　　String[] grid = { "2312", "0233" };
　　String[] stations = { "1 1", "1 1" };

　　String result = ns.location(grid, stations);
　　System.out.println(result);
　}
}
回復更多評論

# re: NewStation(入圍賽750分真題) 2005-12-13 12:10 titian2046

#include <string>
#include <vector>
#include <list>
#include <map>

#include "math.h"
using namespace std;

#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a

#define MAXN 4
#define maxnum 9999999
#define minnum 0.0000001
#define abs(a) ((a>0)?(a):(-1*(a)))
#define eq(a,b) (abs((a)-(b))<minnum)

using namespace std;
#define abs(a) ((a>0)?(a):(-1*(a)))

class NewStation
{
public:
int sts[20][20];
string ret;
vector<string> mgrid;
string location(vector <string> grid, vector <string> stations)
{

mgrid = grid;
int i,j,r=-1,c=0;

init(stations);
long mindist = alldis();
long k;

for (i=0;i<20;i++)
{
for (j=0;j<20;j++)
{
if (sts[i][j]!=1)
{
sts[i][j] =1;
k = alldis();
if ( mindist>k)
{
mindist = k;
r = i;
c = j;
}
sts[i][j] =0;
}
}
}
if (r==-1)
{
return "";
}
else
{
char s1[20];
sprintf(s1,"%d %d",r,c);
ret.assign(s1);
return ret;
}
};
void init(vector <string> stations)
{
int r,c;
int i;
for (i=0;i<20;i++)
{
for (int j=0;j<20;j++)
sts[i][j] = 0;
}
for (i=0;i<stations.size();i++)
{
sscanf(stations[i].c_str(),"%d %d",&r,&c);
sts[r][c] = 1;
}
}
long alldis()
{
long lret =0,lmin;
int i,j,i1,j1;
int len = strlen(mgrid[0].c_str());
for (i=0;i<mgrid.size();i++)
{
for (j =0;j<len;j++)
{
lmin = 100;
for (i1=0;i1<mgrid.size();i1++)
{
for (j1 =0;j1<len;j1++)
{
if (sts[i1][j1]==1&& (abs(i1-i)+abs(j1-j))<lmin)
{
lmin = (abs(i1-i)+abs(j1-j));
}
}
}
lret+= (mgrid[i][j]-'0')*lmin;
}
}
return lret;
};
};
回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網站導航: 博客園 IT新聞 Chat2DB 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中國編程挑戰(zhàn)賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰(zhàn)賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論