1 条题解

  • 0
    @ 2025-4-13 15:48:03

    根据题意,我们可以转化思路。若购买卡牌的其中一种颜色的宝石数量足够,则计数 +1+1 ,若计数达到 33 ,则直接完成购买。

    那么我们可以开三个数组和全局指针,分别对红宝石、绿宝石、蓝宝石的购买数量从小到大进行排序。当卡牌发生购买时,对于每一个数组,我们从上一次遍历的位置开始右移即可遍历,若宝石数量足够则计数 +1+1 ,若计数达到 33 ,则可以直接购买。

    时间复杂度:O(nlogn)O(nlogn)

    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
    上传者