CodeForces 1614B - Divan and a New Project (Java)

문제 : https://codeforces.com/contest/1614/problem/B

 

 

  어려워 보일 수 있는데, 더 많이 방문할수록 가까이 두면 된다.

예를들어 다음의 경우를 보자.

 

5

3 8 10 6 1

 

그럼 얘네들을 더 많이 방문하는 순서대로 정렬해보면 10 > 8 > 6 > 3 > 1이 된다.

그리고 시작지점을 '0'에 둔다고 해보자. 그럼 다음과 같이 배치하면 전체 거리가 최소가 된다.

 

즉 로직은 다음과 같다.

 

1. 들어온 값에 대해 내림차순으로 정렬한다. 이 때, 처음 들어왔던 순서를 알아야 정렬하더라도 처음 들어온 순서에 맞게 출력해줄 수 있다.

 

2. 시작점을 0으로 잡고, '1'에서 정렬한 순서대로 거리가 짧은곳에 둔다. (+1 -> -1 -> +2 -> -2 -> +3 -> ...) 시작점을 0으로 잡은 이유는, 그러면 거리를 계산할 때 거리를 빼는 연산을 안해도 되기 때문이다.

 

3. 처음 입력이 들어온 순서대로 '2'에서 정한 위치를 출력한다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
public class Main extends FastInput {
    StringBuilder answer = new StringBuilder();
 
    class Pos {
        int idx, a;
        public Pos(int idx, int a) {
            this.idx = idx;
            this.a = a;
        }
    }
 
    private void solve() throws Exception{
        int n = nextInt();
        ArrayList<Pos> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(new Pos(i, nextInt()));
        }
        Collections.sort(arr, new Comparator<Pos>() {
            @Override
            public int compare(Pos o1, Pos o2) {
                return o2.a - o1.a;
            }
        });
 
        int[] crd = new int[n];
        long sum = 0;
        int dist = 1;
        for (int i = 0; i < n; i++) {
            Pos cur = arr.get(i);
            if ((i&1)==0) {
                crd[cur.idx] = dist;
            } else {
                crd[cur.idx] = -dist;
                dist++;
            }
            sum += 1l * Math.abs(crd[cur.idx]) * cur.a * 2;
        }
        answer.append(sum).append('\n').append(0).append(' ');
        for (int i = 0; i < n; i++) {
            answer.append(crd[i]).append(' ');
        }
        answer.append('\n');
    }
 
    private void solution() throws Exception {
        int t = nextInt();
        while (t-->0) {
            solve();
        }
        System.out.print(answer);
    }
 
    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}
 
class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final int MAX_CHAR_LEN_FOR_NEXT_LINE = 80;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;
 
    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }
 
    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }
 
    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}