侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 154 阅读 / 630 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

卡牌 - 蓝桥云课


问题描述

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

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

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

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

输入格式

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

第二行为 nn 个正整数 ai,a2,,ana_i, a_2, \dots, a_n

第三行为 nn 个正整数 ai,a2,,ana_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,43,3,3,4 , 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

评测用例规模与约定

对于 3030% 的数据, 保证 n2000n\le2000;

对于 100100% 的数据, 保证 n2×105;ai,bi2n;mn2n≤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);
    }
}
0

评论区