Problem E 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1547/problem/E

첫 번째 방부터 차례대로 계산해 나간다.

첫 번째 방을 들어가기 전에는 모든 에어컨은 오른쪽에 위치해 있다.

첫 번째 방을 기준으로 각 에어컨의 온도를 계산한 값과 에어컨의 위치를 온도 기준 오름차순 형태로 저장한다.

방을 차례대로 방문하다 보면 에어컨이 있는 방을 지나치게 되고,

이때 해당 에어컨은 계산하는 방을 기준으로 왼편으로 이동하게 된다.

오른쪽으로 이동하면서 계산하게 되면 오른쪽 편에 있는 에어컨들의 온도는 방과 점점 가까워지므로 1도씩 낮아지고

왼편에 있는 에어컨들의 온도는 방과 점점 멀어지므로 1도씩 높아진다.

여기서 추가 조건은 방의 온도는 에어컨들의 온도 중 가장 낮은 온도가 된다는 것이다.

정렬했을 때 첫 번째 에어컨이 가장 낮은 온도이고 방을 이동하더라도 오른쪽 편에 있는 한 변하지 않는다.

( 이동하더라도 오른쪽 편 에어컨들은 항상 똑같이 -1도가 되므로 )

처음에는 왼편에 에어컨이 없다. 하지만 에어컨이 있는 방에 도착하는 순간 해당 에어컨은 왼편의 에컨이 된다.

왼편의 에어컨은 하나만 알면 된다. 이유는 왼편에서 가장 낮은 온도의 에어컨 정보만 알면 되고,

오른쪽 편의 에어컨은 왼편으로 이동하는 경우가 있지만 왼편의 에어컨들은 오른쪽 편으로 이동할 일이 없고,

왼편의 에어컨들도 방을 이동할 때마다 모두 똑같이 +1도가 되므로 가장 낮은 에어컨이 바뀔 일이 없다.

( 새로 왼편으로 이동하는 에어컨만 확인하면 된다. )

따라서 방마다 왼편의 에어컨의 제일 낮은 온도와 오른쪽 편의 에어컨의 제일 낮은 온도 중 낮은 온도를 방의 온도로 정한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
bool comp(pair<int, int> lhs, pair<int, int> rhs) {
    if (lhs.second < rhs.second)
        return true;
    return false;
}
 
int main() {
 
    int q;
    cin >> q;
 
    while (q--) {
 
        int n, k;
        cin >> n >> k;
 
        // first: position, second: temperature
        vector<pair<int, int>> v(k + 1);
        vector<int> check(k + 1, 0);
        vector<int> ans(n);
 
        map<int, int> m;
 
        for (int i = 1; i <= k; i++) {
            cin >> v[i].first;
        }
        for (int i = 1; i <= k; i++) {
            cin >> v[i].second;
            v[i].second += v[i].first - 1;
        }
 
        sort(v.begin(), v.end(), comp);
 
        for (int i = 1; i <= k; i++)
            m[v[i].first] = i;
 
        int curIndex = 1;
        int left = 1000300000;
        int minusValue = 0;
 
        for (int room = 1; room <= n; room++) {
 
            if (m[room] > 0) {
                // the room have a air conditionor.
                check[m[room]] = 1;
 
                if (left > v[m[room]].second - minusValue)
                    left = v[m[room]].second - minusValue;
 
                if (curIndex == m[room]) {
                    // min temperature at right side.
 
                    bool isAC = false;
                    for (int i = curIndex + 1; i <= k; i++) {
                        if (check[i] == 0) {
                            curIndex = i;
                            isAC = true;
                            break;
                        }
                    }
 
                    if (isAC == false)
                        curIndex = -1;
                }
            }
 
            if (curIndex == -1) {
                // There is no air conditionor at right side.
                ans[room - 1] = left;
            }
            else {
                if (left < v[curIndex].second - minusValue)
                    ans[room - 1] = left;
                else
                    ans[room - 1] = v[curIndex].second - minusValue;
            }
 
            minusValue++;
            left++;
        }
 
        for (auto a : ans)
            cout << a << " ";
        cout << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기