首页 > 试题广场 >

小红玩纸牌

[编程题]小红玩纸牌
  • 热度指数：232 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红最近迷上了纸牌。纸牌有黑桃（Spade）、红桃（Heart）、方块（Diamond）、梅花（Club）四种花色，并且每张纸牌上面写了一个正整数。小红拿到了许多牌，准备玩以下游戏：

每次操作在这堆牌中任取5张牌，计算这5张牌的分数，然后将其丢弃（丢弃的牌不可再次选取）。
为了简化，本题仅计算同花顺这一牌型：即取出的5张牌构成同花顺，则可以获得1分。其他牌型均不得分。
所谓同花顺，即五张牌花色相同，且排序后满足a_{i}+1=a_{i+1}。

小红想知道，经过若干次操作后，自己最多可以得到多少分？
请注意，同一个牌型可能出现多次！

输入描述:
第一行输入一个正整数n，代表牌堆中牌的种类（如果两张牌的花色或数值不同，则认为种类不同）。
接下来的n行，每行输入两个正整数：a_i和cnt_i和一个字符c_i，分别代表每种牌的大小、数量以及花色。
1\leq n \leq 10^5
1\leq a_i,cnt_i \leq 10^9
c_i∈{'S','H','D','C'}，代表扑克牌的四种花色：黑桃（Spade）、红桃（Heart）、方块（Diamond）、梅花（Club）。
保证每个种类的牌在输入中只出现了一次。


输出描述:
一个整数，代表小红可以最多获得的分数。
示例1

输入

6
1 1 S
2 2 S
3 2 S
4 2 S
5 2 S
1 10 H

输出

1

说明

可以取到一个同花顺：[1S,2S,3S,4S,5S]。虽然有10个红桃1，但无法和其他牌凑成同花顺
示例2

输入

6
1 1 H
2 2 H
3 2 H
4 2 H
5 2 H
6 10 H

输出

2

说明

可以取两次：[1H,2H,3H,4H,5H]和[2H,3H,4H,5H,6H]。
算法知识视频讲解
添加回答
xiaoming1235头像 xiaoming1235
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+7;

// 贪心
void solve() {
    int n;
    cin >> n;
    vector<pair<int,int>>S,H,D,C;
    for(int i=1;i<=n;i++){
        int cnt,num;
        char ch;
        cin >> num >> cnt >> ch;
        if(ch == 'S') {
            S.push_back({num,cnt});
        }else if(ch=='H'){
            H.push_back({num,cnt});
        }else if(ch == 'D'){
            D.push_back({num,cnt});
        }else {
            C.push_back({num,cnt});
        }
    }
    sort(S.begin(),S.end());
    sort(H.begin(),H.end());
    sort(D.begin(),D.end());
    sort(C.begin(),C.end());
   
    int res=0;
    for(int i=0;i<S.size();i++){
     
        if(i+4<S.size()){
            bool ok=true;
            for(int j=i;j+1<=i+4;j++){
               if(S[j+1].first-S[j].first != 1){
                ok=false;
                break;
               }
            }
             
            if(ok){ // 是顺子
               int mi=S[i].second;
               for(int j=i;j<=i+4;j++){
                mi=min(mi,S[j].second);
               }
               res+=mi;
               for(int j=i;j<=i+4;j++){
                S[j].second-=mi;
               }
            }
 
        }
    }

        for(int i=0;i<H.size();i++){
        if(i+4<H.size()){
            bool ok=true;
            for(int j=i;j+1<=i+4;j++){
               if(H[j+1].first-H[j].first != 1){
                ok=false;
                break;
               }
            }
            if(ok){ // 是顺子
               int mi=H[i].second;
               for(int j=i;j<=i+4;j++){
                mi=min(mi,H[j].second);
               }
               res+=mi;
               for(int j=i;j<=i+4;j++){
                H[j].second-=mi;
               }
            }
        }
    }
        for(int i=0;i<D.size();i++){
        if(i+4<D.size()){
            bool ok=true;
            for(int j=i;j+1<=i+4;j++){
               if(D[j+1].first-D[j].first != 1){
                ok=false;
                break;
               }
            }
            if(ok){ // 是顺子
               int mi=D[i].second;
               for(int j=i;j<=i+4;j++){
                mi=min(mi,D[j].second);
               }
               res+=mi;
               for(int j=i;j<=i+4;j++){
                D[j].second-=mi;
               }
            }
        }
    }
        for(int i=0;i<C.size();i++){
        if(i+4<C.size()){
            bool ok=true;
            for(int j=i;j+1<=i+4;j++){
               if(C[j+1].first-C[j].first != 1){
                ok=false;
                break;
               }
            }
            if(ok){ // 是顺子
               int mi=C[i].second;
               for(int j=i;j<=i+4;j++){
                mi=min(mi,C[j].second);
               }
               res+=mi;
               for(int j=i;j<=i+4;j++){
                C[j].second-=mi;
               }
            }
        }
    }
    cout << res << '\n';
}

signed main() {
   solve();
    return 0;
}
发表于 2025-08-12 10:05:26 回复(0)
提交观点

问题信息

贪心 数组 字节跳动 双指针
来自：2024秋招-字节跳动...
难度：
1条回答 83浏览

热门推荐

相关试题

小红玩纸牌

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号