【贪心, 暴力】卡牌【蓝桥杯】

题目

卡牌 - 蓝桥云课

---

问题描述

这天, 小明在整理他的卡牌。

他一共有 $n$ 种卡牌, 第 $i$ 种卡牌上印有正整数数 $i(i \in [1, n])$, 且第 $i$ 种卡牌 现有 $a_i$ 张。

而如果有 $n$ 张卡牌, 其中每种卡牌各一张, 那么这 $n$ 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 $m$ 张空白牌, 他可以在上面写上数 $i$, 将其当做第 $i$ 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 $i$ 种牌最多手写 $b_i$ 张。

请问小明最多能凑出多少套牌?

输入格式

输入共 3 行, 第一行为两个正整数 $n, m$ 。

第二行为 $n$ 个正整数 $a_i, a_2, \dots, a_n$。

第三行为 $n$ 个正整数 $a_i, a_2, \dots, a_n$ 。

输出格式

一行, 一个整数表示答案。

样例输入

4 5
1 2 3 4
5 5 5 5

样例输出

3

样例说明

这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 $3,3,3,4$ , 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

评测用例规模与约定

对于 $30$ 的数据, 保证 $n\le2000$;

对于 $100$ 的数据, 保证 $n≤2×10^5; a_i, b_i \le 2n; m \le n^2$ 。

运行限制

• 最大运行时间：1s
• 最大运行内存：512M

解题

方法一：贪心 暴力

思路

把牌按套遍历，缺了就补，每遍历出一套牌答案加一，直到凑不出一套完整的牌为止。

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        long m = (long) in.nval;
        int[] a = new int[n], b = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            b[i] = (int) in.nval;
        }
        int ans = 0;
        outer: while (true) {
            for (int i = 0; i < n; ++i) {
                if (a[i] != 0) --a[i];
                else {
                    if (b[i] != 0 && m != 0L) {
                        --b[i];
                        --m;
                    } else break outer;
                }
            }
            ++ans;
        }
        System.out.println(ans);
    }
}