1 条题解
-
0
根据题意,我们可以转化思路。若购买卡牌的其中一种颜色的宝石数量足够,则计数 ,若计数达到 ,则直接完成购买。
那么我们可以开三个数组和全局指针,分别对红宝石、绿宝石、蓝宝石的购买数量从小到大进行排序。当卡牌发生购买时,对于每一个数组,我们从上一次遍历的位置开始右移即可遍历,若宝石数量足够则计数 ,若计数达到 ,则可以直接购买。
时间复杂度:
const int N = 2e5 + 10, oo = 1e9 + 7; int n, m, k; struct card { int id, r, g, b; char s; bool operator==(const card &o) const { return id == o.id; } }; bool cmpr(card x, card y) { return x.r < y.r; } bool cmpg(card x, card y) { return x.g < y.g; } bool cmpb(card x, card y) { return x.b < y.b; } card ra[N], ga[N], ba[N]; int r, g, b, ir, ig, ib; int cnt[N]; void check() { bool f = false; for (int i = ir; i <= n; i++) { int id = ra[i].id; char s = ra[i].s; if (ra[i].r <= r) { if (i == n) ir = n + 1; cnt[id]++; } else { ir = i; break; } if (cnt[id] == 3) { if (s == 'R') r++; else if (s == 'G') g++; else b++; f = true; } } // 已省略其余两个相同部分 // if (f) check(); } void solve() { cin >> n; for (int i = 1; i <= n; i++) { card now; cin >> now.s >> now.r >> now.g >> now.b; now.id = i; ra[i] = now; ga[i] = now; ba[i] = now; } sort(ra + 1, ra + 1 + n, cmpr); sort(ga + 1, ga + 1 + n, cmpg); sort(ba + 1, ba + 1 + n, cmpb); r = g = b = 0; ir = ig = ib = 1; check(); int ans = 0; for (int i = 1; i <= n; i++) if (cnt[i] == 3) ans++; cout << ans << endl; }
- 1
信息
- ID
- 4
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者