https://www.acmicpc.net/problem/12016
12016번: 라운드 로빈 스케줄러
첫째 줄에 작업의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 각 작업을 수행해야하는 시간이 공백으로 구분되어 주어진다. 각 작업을 수행해야하는 시간은 1보다 크거나 같고, 1,000,000,000보다
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/364
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)
1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트
rudalsd.tistory.com
1. 작업의 각 번호의 값을 1로 대입해 Segment Tree를 채웁니다.
2. 작업 수행 시간을 입력받고, 작업 수행 시간을 기준으로 오름차순으로, 작업의 번호를 기준으로 내림차순으로 정렬합니다.
3. 현재까지 작업한 작업의 개수를 Cur에 저장하고, 현재 같은 작업수를 가진 작업들의 수를 cnt, 현재 같은 작업수를 가진 작업들과 이전의 같은 작업수를 가진 작업들과의 차를 cur에 저장하고, 현재 남아있는 작업의 개수를 Cnt에 저장합니다.
4. 이전 작업의 수행 시간과 현재 작업의 수행 시간이 같다면 cnt++를 수행하고, 해당 작업 번호의 segment tree 노드의 값을 -1 해주고, ans[ arr[ i ].second ] = Cur + getTree(N, N + arr[ i ].second - 1) + cur * Cnt 의 식을 이용하여 ans배열을 채웁니다.
5. 이전 작업의 수행 시간과 현재 작업의 수행 시간이 다르다면
Cur += Cnt * (cur + 1);
Cnt -= cnt;
cnt = 0;
cur = arr[ i ].first - arr[ i - 1 ].first - 1;
temp = arr[ i ].first;
i--;
를 수행해줍니다.
6. ans를 출력해 줍니다.
[ 소스코드 ]
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 | #include<iostream> #include<algorithm> #define ll long long using namespace std; int N; int segTree[200000]; pair<int, int> arr[100001]; ll ans[100001]; bool cmp(pair<int, int> left, pair<int, int> right) { if (left.first == right.first) return left.second > right.second; return left.first < right.first; } void updateTree(int idx, int diff) { while (idx) { segTree[idx] += diff; idx >>= 1; } } int getTree(int l, int r) { int ret = 0; while (l <= r) { if (l & 1) { ret += segTree[l]; l++; } if (~r & 1) { ret += segTree[r]; r--; } l >>= 1; r >>= 1; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 1; i <= N; i++) { updateTree(N + i - 1, 1); cin >> arr[i].first; arr[i].second = i; } sort(arr + 1, arr + N + 1, cmp); int temp = arr[1].first; int cnt = 0; int Cnt = N; int cur = arr[1].first - 1; ll Cur = 0; for (int i = 1; i <= N; i++) { if (temp == arr[i].first) { cnt++; ans[arr[i].second] = Cur + (ll)getTree(N, N + arr[i].second - 1) + 1LL * cur * Cnt; updateTree(N + arr[i].second - 1, -1); } else { Cur += 1LL * Cnt * (1LL * cur + 1); Cnt -= cnt; cnt = 0; cur = arr[i].first - arr[i - 1].first - 1; temp = arr[i].first; i--; } } for (int i = 1; i <= N; i++) { cout << ans[i] << '\n'; } } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 13565번 - 침투 (C++) (0) | 2023.09.22 |
|---|---|
| [ 백준 ] 12761번 - 돌다리 (C++) (0) | 2023.09.21 |
| [ 백준 ] 17609번 - 회문 (C++) (0) | 2023.09.19 |
| [ 백준 ] 5569번 - 출근 경로 (C++) (0) | 2023.09.18 |
| [ 백준 ] 13398번 - 연속합 2 (C++) (0) | 2023.09.17 |