比赛 2026.5.30 评测结果 AAAAAAAAAAAAAAAAATTT
题目名称 雨和卡布奇诺 最终得分 85
用户昵称 LikableP 运行时间 5.041 s
代码语言 C++ 内存使用 6.31 MiB
提交时间 2026-05-30 11:36:52
显示代码纯文本
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>

const int MAXN = 1e5 + 10;

struct Support {
  struct CoffeeMachineData {
    int type;
    int count;
    CoffeeMachineData(int type = 0, int count = 0): type(type), count(count) {}
  };
  std::vector<CoffeeMachineData> require;
  std::vector<CoffeeMachineData> offer;
  
  void sort() {
    std::sort(require.begin(), require.end(), [](CoffeeMachineData x, CoffeeMachineData y) {
      if (x.count != y.count) return x.count < y.count;
      return x.type < y.type;
    });
  }
};

int n, m;
std::vector<Support> support;
std::map<int, long long> coffeeMachineCount;

bool MeetRequirement(std::vector<Support::CoffeeMachineData> &require) {
  for (auto req : require) {
    if (coffeeMachineCount.find(req.type) == coffeeMachineCount.end()) return false;
    if (coffeeMachineCount[req.type] < req.count) return false;
  }
  return true;
}

void AddCoffeeMachine(std::vector<Support::CoffeeMachineData> &offer) {
  for (auto off : offer) {
    coffeeMachineCount[off.type] += off.count;
  }
}

int main() {
  freopen("Cappuccino.in", "r", stdin);
  freopen("Cappuccino.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1, type, count; i <= n; ++i) {
    scanf("%d %d", &type, &count);
    coffeeMachineCount[type] = count;
  }
  scanf("%d", &m); support.resize(m);
  for (int i = 0, requirecount, offercount; i < m; ++i) {
    scanf("%d", &requirecount);
    for (int j = 1, type, count; j <= requirecount; ++j) {
      scanf("%d %d", &type, &count);
      support[i].require.emplace_back(type, count);
    }
    scanf("%d", &offercount);
    for (int j = 1, type, count; j <= offercount; ++j) {
      scanf("%d %d", &type, &count);
      support[i].offer.emplace_back(type, count);
    }
    support[i].sort();
  }
  
  std::sort(support.begin(), support.end(), [](Support &x, Support &y) {
    return x.require.size() < y.require.size();
  });
  
  int ans = 0, flag = 0;
  do {
    flag = 0;
    for (std::vector<Support>::iterator it = support.begin(); it != support.end(); ++it) {
      if (MeetRequirement(it->require)) {
        flag = 1; ++ans;
        AddCoffeeMachine(it->offer);
        support.erase(it);
        if (it == support.end()) break;
      }
    }
  } while (flag);
  
  printf("%d\n", ans);
  return 0;
}