264 words
1 minutes
[BOJ] 컵라면
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 256MB | 1 ≤ N ≤ 200,000 | Sort, Greedy |
문제는 대놓고 그리디 냄새를 냈지만, 생각보다 간단한 문제임에도 불구하고 오래걸렸다…
간단히 현재 시간까지의 최대값을 유지하면서 진행을 해버리면 됩니다~~
정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll = long long;
int N;
pair<int, int> problems[200'001];
int visited[200'001];
bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second < b.second;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for(int i = 0; i < N; i++){
cin >> problems[i].second >> problems[i].first;
// q.push({problems[i].second, problems[i].first});
// visited[i+1] = -1;
}
sort(problems, problems+N, compare);
q.push(problems[0]);
for(int i = 1; i < N; i++){
auto [cost, current] = problems[i];
if(current > q.size()){
q.push(problems[i]);
// cout <<"size: " << q.size() << " " << current << "\n";
}
else{
// cout << "cost: " << cost << " " << q.top().first << "\n";
if(cost <= q.top().first) continue;
// cout << "cost: " << cost << " " << q.top().first << "\n";
q.pop();
q.push({problems[i]});
}
// cout << i << "\n";
}
int result = 0;
while(!q.empty()){
// cout << q.top().first << " " << q.top().second << "\n";
result += q.top().first; q.pop();
}
cout << result;
return 0;
}