ジュエリー泥棒

17718 ワード
1202 acmicpc ジュエリー泥棒 boj テキストリンク
Problem link: https://www.acmicpc.net/problem/1202
DPで解くという強迫から脱すれば、すぐに解ける.
考えてみましょう.まず小さな包装をいっぱいにします.
今見ているバッグに入れる宝石の候補者を見つけたら、その中で一番高い宝石を記入すればいいです.
どうせ次のカバンには候補者が入っているし、欲しがる財産も満たされる.
このとき、次のような問題が発生しました.
  • 「でしょ?!、宝石の中(1)現在見ているバッグの重量制限範囲内、(2)一番高いやつを見つけたい」
  • 「セグメントツリーを使った改行に似ています!
    • このタイプの問題は、通常、クエリー/ソートを2つの基準で行うよりも、1つの基準を切り替えて順序を調整すればよいということです.
    説明が哲学的すぎて、最終的には以下のように解釈される.
  • パケットを重量制限基準とし、昇順に並べた.
  • 宝石を重量制限基準とし、昇順に並べた.
    • 前から順番に見て
  • パック
  • リュックサックを入れる宝石を優先行列(価格基準)
    • に入れるようになりました
  • を全部入れて、上部の宝石を今見ているバッグに入れればいいです.
    • 宝石を重量制限基準に並べて交換することは、交換順序によって一つの基準を調整することと理解できる.
    #include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdint>

using namespace std;

class Gem
{
private:
  int weight_;
  int price_;

public:
  Gem(void)
  {
  }
  Gem(const int weight, const int price) : weight_(weight), price_(price)
  {
  }

  const int weight(void) const
  {
    return weight_;
  }

  const int price(void) const
  {
    return price_;
  }

  static bool CompareWeight(const Gem& lhs, const Gem& rhs)
  {
    return lhs.weight() < rhs.weight();
  }

  bool operator<(const Gem& rhs) const
  {
    return price_ < rhs.price();
  }
};

class Bag
{
private:
  int capacity_;

public:
  Bag(void)
  {
  }
  Bag(const int capacity) : capacity_(capacity)
  {
  }

  const int capacity(void) const
  {
    return capacity_;
  }

  bool operator<(const Bag& rhs) const
  {
    return capacity_ < rhs.capacity();
  }
};

int64_t Solve(vector<Gem>& gems, vector<Bag>& bags)
{
  sort(gems.begin(), gems.end(), Gem::CompareWeight);
  sort(bags.begin(), bags.end());

  priority_queue<Gem> pq;

  int64_t ret = 0;
  size_t gem_idx = 0;
  for (const auto& bag : bags)
  {
    while (gem_idx < gems.size())
    {
      if (bag.capacity() >= gems[gem_idx].weight())
      {
        pq.emplace(gems[gem_idx]);
        ++gem_idx;
      }
      else
      {
        break;
      }
    }

    if (!pq.empty())
    {
      ret += pq.top().price();
      pq.pop();
    }
  }

  return ret;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  int n, k;
  cin >> n >> k;

  vector<Gem> gems;
  for (int it = 0; it < n; ++it)
  {
    int weight, price;
    cin >> weight >> price;

    gems.emplace_back(weight, price);
  }

  vector<Bag> bags;
  for (int it = 0; it < k; ++it)
  {
    int capacity;
    cin >> capacity;
    bags.emplace_back(capacity);
  }

  // Solve
  cout << Solve(gems, bags) << '\n';

  return 0;
}
    [Extension] UIViewController + makeAlert 🍒
    JSでのブレ止めとスロットル