U E D R , A S I H C RSS

1R/2016_09_24

Difference between r1.3 and the current

@@ -16,22 +16,8 @@

using namespace std;

class PairCompare
{
public:
bool operator()(pair<int,int> &p1, pair<int,int> &p2){
if(p1.first == p2.first){
return p1.second < p2.second;
}
else{
return p1.first < p2.first;
}
}
};
 
int main(){
priority_queue<pair<int, int>, vector<pair<int, int>>, PairCompare> que;
priority_queue<pair<int, int>> que;
multiset<int> bag;
int N, K;
long long int ans = 0;
@@ -59,12 +45,57 @@
}
}}}
== 박인서 ==
{{{
#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;
}
}}}

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==
* 가치가 큰 보석 부터 넣을 수 있는 가장 작은 가방에 차례대로 넣는다.
* 끝
* 가치는 1 ≤ V ≤ 1,000,000이고 보석 수는 1 ≤ N ≤ 300,000이기 때문에 int범위를 벗어 날 수 있으니 주의 해야한다.
== 박인서 ==
* 원준이 아이디어와 동일
* priority_queue 대신 vector와 sort를 이용

== 곽정흠 ==




1. 오늘의 문제

2. 참가자


3. 코드

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;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준

  • 가치가 큰 보석 부터 넣을 수 있는 가장 작은 가방에 차례대로 넣는다.

  • 가치는 1 ≤ V ≤ 1,000,000이고 보석 수는 1 ≤ N ≤ 300,000이기 때문에 int범위를 벗어 날 수 있으니 주의 해야한다.

4.2. 박인서

  • 원준이 아이디어와 동일
  • priority_queue 대신 vector와 sort를 이용

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:07
Processing time 0.0589 sec