본문 바로가기
알고리즘/그리디 알고리즘

마감시간을 가지는 작업 더블릿

by tryotto 2019. 2. 20.
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <functional>
using namespace std;
vector<pair<int, int> > arr(20000);
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
if (a.first == b.first)
return a.second > b.second;
return a.first > b.first;
}
int main() {
int t, m, idx = 1;
while (scanf("%d %d", &t, &m) != EOF) {
arr[idx].first = t;
arr[idx].second = m;
idx++;
}
sort(&arr[1], &arr[idx], compare);
int time = 0, rst = 0, end = arr[1].first;
for (int i = 1; i < idx; i++) {
if (end == 0)
break;
else
end--;
time = arr[i].first;
rst += arr[i].second;
// 마감시간이 time 인 arr pair들의 마감시간들을 1씩 줄여준다
for (int j = i + 1; j < idx; j++) {
if (time != arr[j].first) {
break;
}
arr[j].first = time - 1;
}
//다 줄인 뒤엔, 다시 한 번 더 소팅을 해준다
sort(&arr[i + 1], &arr[idx], compare);
}
printf("%d", rst);
}


'알고리즘 > 그리디 알고리즘' 카테고리의 다른 글

11399 ATM  (0) 2019.06.22
테이블 옮기기 더블릿  (0) 2019.02.20
knapsack 더블릿  (0) 2019.02.20
mixing milk 더블릿  (0) 2019.02.20
(복습필요) 11000 강의실 배정  (0) 2019.02.19