Difference between r1.6 and the current
@@ -45,6 +45,47 @@
}
}}}
== 박인서 ==
== 곽정흠 ==
}}}
== 박인서 ==
{{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef struct _jewel { int m, v; } j;
std::vector<j> jewel;
std::multiset<int> c;
int main() {
int n, k;
std::cin >> n >> k;
for (int i = 0; i < n; i++) {
j t;
std::cin >> t.m >> t.v;
jewel.push_back(t);
}
std::sort(jewel.begin(), jewel.end(), [](j a, j b) {return a.v < b.v; });
for (int i = 0; i < k; i++) {
int t;
std::cin >> t;
c.insert(t);
}
long long int res = 0;
while (jewel.size() && c.size()) {
j t = jewel[jewel.size() - 1];
jewel.pop_back();
std::multiset<int>::iterator it = c.lower_bound(t.m);
if (it != c.end()) {
res += t.v;
c.erase(it);
}
}
std::cout << res;
return 0;
}
}}}
== 곽정흠 ==
@@ -54,5 +95,7 @@
* 끝
* 가치는 1 ≤ V ≤ 1,000,000이고 보석 수는 1 ≤ N ≤ 300,000이기 때문에 int범위를 벗어 날 수 있으니 주의 해야한다.
== 박인서 ==
== 곽정흠 ==
* 가치는 1 ≤ V ≤ 1,000,000이고 보석 수는 1 ≤ N ≤ 300,000이기 때문에 int범위를 벗어 날 수 있으니 주의 해야한다.
== 박인서 ==
* 원준이 아이디어와 동일
* priority_queue 대신 vector와 sort를 이용
== 곽정흠 ==
3.1. 15이원준 ¶
#include<iostream> #include<algorithm> #include<set> #include<utility> #include<queue> using namespace std; int main(){ priority_queue<pair<int, int>> que; multiset<int> bag; int N, K; long long int ans = 0; cin >> N >> K; for(int i = 0; i<N; i++){ int tmp1, tmp2; scanf("%d %d", &tmp1, &tmp2); que.push(make_pair(tmp2, tmp1)); } for(int i = 0; i<K; i++){ int tmp; scanf("%d", &tmp); bag.insert(tmp); } while(que.size() && bag.size()){ pair<int,int> tmp = que.top(); que.pop(); auto p = bag.lower_bound(tmp.second); if(p != bag.end()){ ans+= tmp.first; bag.erase(p); } } cout<< ans<<endl; }
3.2. 박인서 ¶
#include <iostream> #include <vector> #include <algorithm> #include <set> typedef struct _jewel { int m, v; } j; std::vector<j> jewel; std::multiset<int> c; int main() { int n, k; std::cin >> n >> k; for (int i = 0; i < n; i++) { j t; std::cin >> t.m >> t.v; jewel.push_back(t); } std::sort(jewel.begin(), jewel.end(), [](j a, j b) {return a.v < b.v; }); for (int i = 0; i < k; i++) { int t; std::cin >> t; c.insert(t); } long long int res = 0; while (jewel.size() && c.size()) { j t = jewel[jewel.size() - 1]; jewel.pop_back(); std::multiset<int>::iterator it = c.lower_bound(t.m); if (it != c.end()) { res += t.v; c.erase(it); } } std::cout << res; return 0; }