我将尝试指出您可以遵循的策略，以实现所需的 1 秒响应时间。当然，它必须被实施以确保它符合这个要求。
该解决方案依赖于以下事实：
基本上，给定位置 P 的加权距离 WP 总和，每个怪物将通过增加或减去 WP 的 1 倍强度来对 P 邻居的加权距离总和做出贡献。如果邻居比 P 更接近怪物，则增加力量，如果距离更远，则减少力量。
考虑到这一事实，解决方案在于计算初始步骤上某个初始位置的加权距离之和，并根据先前为其邻居计算的值计算其他位置的加权距离之和。
除了计算初始位置的值外，我们还必须在初始步骤中定义：
- 一个方向（例如顺时针），我们将在该方向上遍历位置以计算加权距离的总和
- 在定义的方向上穿越时，我们将获得更远（添加）的怪物的力量总和（SADD）；
- 在定义的方向上穿越时，我们将更接近（减去）的怪物的力量总和（SSUB）；
然后，从初始位置的邻居开始，遍历定义方向上的所有位置，并且对于每个位置，我们更新 SADD 和 SSUB（当我们遍历圆形路径时，一些越来越近的怪物开始变得越来越远，反之亦然反之亦然）并将 (SADD - SSUB) 添加到为前一个邻居计算的值上。
因此，我们可以计算所有位置的加权距离之和，而不必为每个位置遍历所有怪物。
我用 Java 实现了该解决方案的初始版本。
下面的类代表一个怪物：
class Monster {
private long strenght;
private int position;
// omitting getters and setters...
}
下面的类代表正方形边的位置：
class SquareSidePositions {
private List<Monster>[] positionWithMosters;
private List<Monster> monstersOnSquareSides = new ArrayList<Monster>();
@SuppressWarnings("unchecked")
public SquareSidePositions(int numberOfPositions) {
positionWithMosters = new LinkedList[numberOfPositions];
}
public void add(int position, Monster monster) {
if (positionWithMosters[position] == null) {
positionWithMosters[position] = new LinkedList<Monster>();
}
positionWithMosters[position].add(monster);
monster.setPosition(position);
monstersOnSquareSides.add(monster);
}
public int size() {
return positionWithMosters.length;
}
public boolean hasMonsters(int position) {
return positionWithMosters[position] != null;
}
public long getSumOfStrenghtsOfMonstersOnThePosition(int i) {
long sum = 0;
for (Monster monster : positionWithMosters[i]) {
sum += monster.getStrenght();
}
return sum;
}
public List<Monster> getMonstersOnSquareSides() {
return monstersOnSquareSides;
}
}
最后，通过以下方法进行优化：
public static int findBest(SquareSidePositions positions) {
long tini = System.currentTimeMillis();
long sumOfGettingNearer = 0;
long sumOfGettingFarther = 0;
int currentBestPosition;
long bestSumOfWeight = 0;
long currentSumOfWeight;
final int numberOfPositions = positions.size();
int halfNumberOfPositions = numberOfPositions/2;
long strenghtsOnPreviousPosition = 0;
long strenghtsOnCurrentPosition = 0;
long strenghtsOnPositionStartingGetNearer = 0;
int positionStartGetNearer;
// initial step. Monsters from initial position (0) are skipped because they are at distance 0
for (Monster monster : positions.getMonstersOnSquareSides()) {
// getting nearer
if (monster.getPosition() < halfNumberOfPositions) {
bestSumOfWeight += monster.getStrenght()*monster.getPosition();
sumOfGettingNearer += monster.getStrenght();
} else {
// getting farther
bestSumOfWeight += monster.getStrenght()*(numberOfPositions - monster.getPosition());
sumOfGettingFarther += monster.getStrenght();
}
}
currentBestPosition = 0;
currentSumOfWeight = bestSumOfWeight;
// computing sum of weighted distances for other positions
for (int i = 1; i < numberOfPositions; ++i) {
strenghtsOnPreviousPosition = 0;
strenghtsOnPositionStartingGetNearer = 0;
strenghtsOnCurrentPosition = 0;
positionStartGetNearer = (halfNumberOfPositions + i - 1);
if (positionStartGetNearer >= numberOfPositions) {
positionStartGetNearer -= numberOfPositions;
}
// monsters on previous position start to affect current and next positions, starting to get farther
if (positions.hasMonsters(i-1)) {
strenghtsOnPreviousPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i-1);
sumOfGettingFarther += strenghtsOnPreviousPosition;
}
// monsters on current position will not affect current position and stop to get nearer
if (positions.hasMonsters(i)) {
strenghtsOnCurrentPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i);
currentSumOfWeight -= strenghtsOnCurrentPosition;
sumOfGettingNearer -= strenghtsOnCurrentPosition;
}
// monsters on position next to a half circuit start to get nearer
if (positions.hasMonsters(positionStartGetNearer)) {
strenghtsOnPositionStartingGetNearer = positions.getSumOfStrenghtsOfMonstersOnThePosition(positionStartGetNearer);
sumOfGettingNearer += strenghtsOnPositionStartingGetNearer;
sumOfGettingFarther -= strenghtsOnPositionStartingGetNearer;
}
currentSumOfWeight += sumOfGettingFarther - sumOfGettingNearer;
// if current is better than previous best solution
if (currentSumOfWeight > bestSumOfWeight) {
bestSumOfWeight = currentSumOfWeight;
currentBestPosition = i;
}
}
final long executionTime = System.currentTimeMillis() - tini;
System.out.println("Execution time: " + executionTime + " ms");
System.out.printf("best position: %d with sum of weighted distances: %d\n", currentBestPosition, bestSumOfWeight);
return currentBestPosition;
}
要设置您用作示例的输入，您可以使用：
SquareSidePositions positions = new SquareSidePositions(12);
positions.add(1, new Monster(3));
positions.add(3, new Monster(1));
positions.add(10, new Monster(1));
positions.add(11, new Monster(2));
在初步测试中，该方法在运行 Windows 7 的 Intel Core i5-2400 上执行 100,000 个怪物和 200,000,000 个可能位置需要 771 毫秒。
我使用以下代码来生成此输入：
// I used numberOfMosters == 100000 and numberOfPositions == 200000000
public static SquareSidePositions initializeMonstersOnPositions(int numberOfMonsters, int numberOfPositions) {
Random rand = new Random();
SquareSidePositions positions = new SquareSidePositions(numberOfPositions);
for (int i = 0; i < numberOfMonsters; ++i) {
Monster monster = new Monster(rand.nextInt(10000)+1);
positions.add(rand.nextInt(numberOfPositions), monster);
}
return positions;
}
我希望它对你有帮助！