牛客真題(10)-駒を積む

今日は引き続き牛客、網易の駒を磨きます.
解析:n個の駒の横縦座標を与え,i個の駒を並べた移動距離を出力する.解法は実際には暴力的な解決に似ており,各駒から他のすべての駒までのマンハッタン距離を計算し,移動距離との最小値を更新する.
質問:1、現在の点からすべての点までの距離を一時変数で格納します.2、距離の最小値を計算します.
C++コードを添付します.

#include

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector x(n),y(n);
    for(int i=0;i>x[i];
    for(int i=0;i>y[i];
    priority_queue,greater> pq;
    vector result(n,INT_MAX);
    for(int i=0;i

Pythonコードを添付します.

n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

dist = [float('Inf') for _ in range(n)]
for i in range(n):
    for j in range(n):
        t = 0
        tmp = []
        for k in range(n):
            tmp.append(abs(x[i]-x[k])+abs(y[j]-y[k]))
        tmp.sort()
        for k in range(n):
            t += tmp[k]
            dist[k] = min(dist[k], t)

print(' '.join(map(str, dist)))