[コードテストC+]宝石泥棒


今日の質問


https://www.acmicpc.net/status?user_id=huijae0817&problem_id=1202&from_mine=1

ジュエリー泥棒



方法

  • 最初は単純に宝石の高いものから大きなバッグに入れたいだけで、それを解いてから間違っていました.
  • 以前学んだDeadline Schedulingアルゴリズムを思い出して、問題を解決することができます.
  • Deadline計画は、点数が最も高い最終期限で手配されています.
  • そのため、まず収益(価格)が大きいものを手配しますが、最も適切な位置(私の重量以上の最小値)
  • に手配します.
  • この役割のアルゴリズムは下限であり,下限を簡単に使用するmultisetにパケットの重量を配置した.
  • こうなると、値段の高い順に処分して、値段の高い宝石の重さを下界にします.場所が見つかったら削除され、見つからない場合は次の宝石に移動します.
  • 私の答え

    #include <iostream>
    #include <algorithm>
    #include <set>
    using namespace std;
    const int MAX = 300001;
    pair<int, int> jew[MAX];
    multiset<int> weight;
    int n, k;
    
    // 보석 도둑
    bool cmp(pair<int, int> a, pair<int, int> b){
        return a.second> b.second;
    }
    long long solution(){
        long long answer = 0;
        sort(jew, jew + n, cmp);
        for(int i=0;i<n;i++){
            if(weight.lower_bound(jew[i].first) != weight.end()){
                answer += jew[i].second;
                weight.erase(weight.lower_bound(jew[i].first));
                if(weight.empty())
                    break;
            }
        }
        return answer;
    }

    別の解釈

    #include <iostream>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    int N, K;
    long long res = 0;
    pair<int, int> gem[300000];
    int bag[300000];
    priority_queue<int> pq;
    
    int main(){
    	ios_base::sync_with_stdio(0);
    	cin.tie(0);
    	
    	cin >> N >> K;
    	
    	for(int i=0; i<N; i++)
    		cin >> gem[i].first >> gem[i].second;
    	for(int i=0; i<K; i++)
    		cin >> bag[i];
    	
    	// 보석(무게기준), 가방 오름차순 정렬	
    	sort(gem, gem + N);
    	sort(bag, bag + K);
    	
    	// 무게제한에 맞는 보석 일단 모두 넣음
    	int cnt = 0;   // 들어간 보석 개수  
    	for(int i=0; i<K; i++){
    		while(cnt < N && gem[cnt].first <= bag[i])
    			pq.push(gem[cnt++].second);
    		
    		// 비싼거부터 뺀다. 	
    		if(!pq.empty()){
    			res += pq.top();
    			pq.pop();
    		}
    	}
    	
    	cout << res;
    	
    	
    	return 0;
    }

    学ぶべきところ

  • わあ、こんなに簡単ですね.
  • 重量制限に該当する宝石を入れ、高いものから抽出します.
  • 私は宝石を中心に答えました.この人はかばんを中心に答えました.