CodeForces 1614A - Divan and a Store (Java)

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

 

  

  처음엔 냅색문제로 예상했는데, 생각해보니 그냥 작은 값부터 그리디로 확인해봐도 만족할 것 같아 노선을 변경함!

 

1. 우선 전처리로, 입력으로 들어온 a 중 l 미만이거나 r 초과인 값은 버려버린다.

 

2. '1'에서 걸러서 남겨진 값들을 정렬한다.

 

3. 이제 그리디하게 작은 숫자부터 k에서 빼가면서, 0보다 작아지는 경우 그 전까지 구매할 수 있다.

 

 

코드 : 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];
        int 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 += 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++];
    }
}