思路：贪心

这个题目本质就是在问：给定一个整数数组$a$，给定一个操作:

$a[i] , a[i+1] , a[i+2] , a[i + 3] , a[i + 4]$ 整体减1。问最多能够进行多少次操作？

显然从小往大拿是最优的。反过来想 ， 考虑如果存在$1,2,3,4,5$ 这个五个序号可以操作。但是我们却忽略掉$1$ 的存在, 这样会把$1$ 所构成的操作给浪费掉。但是把他浪费掉并不能让后续的操作次数增多 。所以能操作就操作一定最优。剩下的就是对过程的模拟。

代码

Java

import java.util.*;
public class Main {
    public static void main (String args[]){
        Scanner sc = new Scanner (System.in);
        int n = sc.nextInt();
        HashMap<String , Long> mp = new HashMap<>(); // 记录牌出现次数
        for (int i = 0 ; i < n ; i++){
            int num = sc.nextInt();
            long cnt = sc.nextLong();
            String s  = sc.next();
            mp.put(s + num , mp.getOrDefault(s + num , (long) 0) + cnt);
        }
        List<String> arr = new ArrayList<>();
        arr.addAll(mp.keySet());
        // 对连击二元组(str , num )进行排序 , 方便后面贪心的线性选取
        arr.sort((x , y) -> {
            long numX = Long.valueOf(x.substring(1));
            String typeX = x.substring(0 , 1);
            long numY = Long.valueOf(y.substring(1));
            String typeY = y.substring(0 , 1);
            if (typeX.equals(typeY)){
                assert numX != numY;
                return  numX - numY < 0 ? -1 : 1;
            }
            return typeX.compareTo(typeY);
        });
        // 贪心的 ， 对于同一种牌，从小往大取五连击
        long ans = 0;
        for (String x : arr){
            String type = x.substring(0, 1);
            long num = Long.valueOf(x.substring(1));
            long mi = Long.MAX_VALUE;
            // 取五连击的最多可能次数
            for (int i = 0 ; i < 5 ; i++){
                String now = type + (num + i);
                mi = Math.min(mi , mp.getOrDefault(now,(long)0));
            }
            // 更新次数
            ans += mi;
            for (int i = 0 ; i < 5 ; i++){
                String now = type + (num + i);
                mp.put(now , mp.getOrDefault(now, (long) 0) - mi);
            }
        }
        System.out.println(ans);
        return ;
    }
}

Python

from collections import defaultdict
# 使用defaultdict来创建一个默认值为0的字典
cnt = defaultdict(int)
arr = []
# 输入连击的数量n
n = int(input())
for _ in range(n):
    x, num, c = map(str, input().split())
    x = int(x)
    num = int(num)
    cnt[c + str(x)] += num
    arr.append((c, x))
# 贪心的从小往大枚举
arr.sort()
ans = 0
for x in arr:
    g = [x[0] + str(x[1] + i) for i in range(5)]  # 枚举当前五连击
    mi = min(cnt[val] for val in g)  # 在这5连击中找到最小的数量
    ans += mi  # 将最小数量加入到结果中
    for val in g:
        cnt[val] -= mi  # 更新剩余牌的数量
print(ans)

C++

#include<bits/stdc++.h>
using namespace std;
int main() {
    map<string, long long> cnt; // 存连击对应的数量
    vector<pair<string, int>> arr; // 连击数组
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, num;
        string c;
        cin >> x >> num >> c;
        cnt[c + to_string(x)] += num;
        arr.push_back(make_pair(c, x));
    }
    sort(arr.begin(), arr.end()); // 排序，以便之后的从小到大贪心
    long ans = 0;
    for (auto& x : arr) { // 贪心根据编号从小往大选
        vector<string> g;
        for (int i = 0; i < 5; i++) { // 构造五连击数组
            g.push_back(x.first + to_string(x.second + i));
        }
        long long mi = 1e10;  // 获取这个五连击的最多可能
        for (auto& val : g) {
            mi = min(mi, cnt[val]);
        }
        ans += mi;
        for (auto& val : g) { // 更新连击数量
            cnt[val] -= mi;
        }
    }
    cout << ans << endl;
    return 0;
}

题目内容

小红最近沉迷音游，他玩的这款音游以钢琴音为主，每个钢琴块都有一个块号，块号最小为 $1$ ，如果连续击中五个号码连续递增的块 ，就会爆一个金币。

举个例子，小红在一个关卡中击中了号码为 1, 2, 3, 4, 5, 6 的块，那么对于 1, 2, 3, 4, 5 这样五个号码连续递增的块，就会爆出一个金币。

当一个关卡进行了很久后，块号会重置，重置后的块号从 $1$ 开始。所以对于一个关卡来说，可能击中多个块号相同的不同块。

注意，这里只要求在同一关卡中，五个块号连续递增的块，即可爆出金币。

由于小红实力超群，他已经通过了四个关卡。现在给出了小红在四个难度关卡 $A$、$B$、$C$ 和 $D$ 中击中的块号，问你在四个关卡中，小红能够获得多少金币。

输入描述

第一行，一个正整数$n(1 \leq n \leq 10^5)$，代表小红在四个关卡中击中的块数。

接下来的$n$行，每行输入两个正整数: $a_i, b_i(1 \leq a_i,b_i \leq 10^9)$，和一个字符$c_i(c_i\in \{'A',B','C','D'\})$，分别代表每个块的块号、数量以及关卡。

输出描述

一个整数， 表示小红小红能够获得的金币数。

样例

输入

11
1 1 A
2 2 A
3 2 A
4 2 A
5 2 A
6 1 A
7 1 B
8 2 B
9 2 B
10 2 B
11 1 B

输出

3

说明

对于关卡 $A$ ，首先 1,2,3,4,5 可以爆出一个金币，然后 2,3,4,5,6 可以爆出一个金币。

对于关卡 $B$ ，7,8,9,10,11 可以爆出一个金币。

总共是 $3$ 个金币。

样例2

输入

5
1 1 C
2 2 C
3 2 C
4 2 C
6 1 C

输出

0

说明

无法得到在同一关卡中，五个连续递增的块，金币数为 0 。