亚洲精品无码久久久久去q,亚洲黄片毛片在线观看,久久亚洲欧洲国产综合

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 閱讀(1683) 評(píng)論(4) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

評(píng)論

# emu的解法 2005-08-23 16:47 emu

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);

    }

}

  回復(fù)  更多評(píng)論

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

遺憾的很，我這個(gè)答案沒有通過google的系統(tǒng)測(cè)試。回復(fù) 更多評(pí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);
　}
}
回復(fù) 更多評(píng)論

# 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ù) 更多評(píng)論

新用戶注冊(cè) 刷新評(píng)論列表


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




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 沒忍住手癢做了一道題，結(jié)果還沒作對(duì)。差點(diǎn)被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國(guó)編程挑戰(zhàn)賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國(guó)編程挑戰(zhàn)賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊(cè)

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

評(píng)論