首页 > 试题广场 >

小球投盒

[编程题]小球投盒

热度指数：3183 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红一共有 $n$ 个盒子，标号为 1 到 $n$ ，小红向盒子里放入小球 $m$ 次，每次进行以下两个操作中的一个：
1. 向编号为 $x$ 的盒子里放入一个小球；
2. 向除了编号为 $x$ 的其他 $n - 1$ 盒子里放入一个小球。
小红想知道，第几次操作之后，所有盒子里至少都有一个小球，如果一直无法达到这个目标，输出 $-1$ 。

输入描述:

第一行两个整数  和 ，表示盒子的数量和操作的次数。
接下来  行，每行两个整数  和 ，表示第  次操作的类型和  的值。

输出描述:

输出一个整数，表示第几次操作之后，所有盒子里至少都有一个小球，如果一直无法达到这个目标，输出 。

示例1

输入

输出

说明

三次操作之后，所有盒子里都至少有一个小球。

示例2

输入

输出

说明

第一次操作后，盒子 1 里有小球。第二次操作后，盒子 1、3 里有小球。
第三次操作后，盒子 1、3 里有小球。
第四次操作后，每个盒子里都有小球。

算法知识视频讲解

Mag1c0nch

发表于 2024-11-21 18:23:51

每次 1 操作之后只有两种情况完成目标，同盒子 x 有过 2 操作，或者所有盒子都有过 1 操作每次 2 操作之后只有两种情况完成目标，同盒子 x 有过 1 操作，或者有其他盒子有过 2 操作可以使用map维护已经操作过的 1 和 2 操作，注意检查某操作是否存在（某个键是否存在）需要使用 coun 展开全文

月薪三千啊

发表于 2024-11-23 22:23:31

读题意可以发现有以下几种情况是可以全部投一遍的：操作1，执行操作1 n 次不同的位置，最后一定是满了的。操作2，可以发现执行了两次不同操作他们的并集就覆盖了全部的盒子操作 1 和操作 2 一起，如果在 i 位置同时执行过了操作 1 和操作 2，那么也全部投满了。统计不同的次数，可以用 set 来展开全文

宿伞之神

发表于 2024-11-21 18:52:38

分类讨论题，用一个set维护1操作，当2操作来到的时候讨论此时是否满足条件即可。 #include<bits/stdc++.h> #define int long long #define double long double #define x first #define y seco 展开全文

道柒

发表于 2024-11-22 10:01:31

我看题解都是用map或者set然后分类讨论，那我发一个使用二分加前缀和的思路。我们可以离线把操作记录下来然后二分最少需要几次可以全部覆盖。每次二分我们可以把前mid次操作通过差分和前缀和完成。具体可以看代码 #include<bits/stdc++.h> using i64 = lon 展开全文

Kato_Shoko

发表于 2024-11-22 17:34:02

#include <iostream> #include <queue> #include <map> #include <set> #include <cmath> #include <cstring> #include &l 展开全文

阿里嘎多懒羊羊桑_

发表于 2024-11-22 18:25:13

题意有n个盒子，可以进行m次操作，每次操作有2种向编号为x的盒子里放一个小球向除了编号x的其他n-1个盒子里放一个小球求第几次操作后，所有盒子里至少都有一个小球思路答案是具有单调性的，因为每次都是往盒子里放小球，第x次操作后，所有的盒子里至少有一个小球的话，那么第x+1操作后，也肯定满足这个条件。而展开全文

Feijoa_Li

发表于 2024-11-22 21:43:40

看了一眼大家的思路，誒，怎么都是二分或者map/set但是好像可以只用数组来解决吧用a数组来维护操作1只放一个球用b数组来维护操作2用check来确定我们是否进行过操作2用cnt来记录我们已经放入了多少个球那么该如何判断进行一次操作后是否所有盒子都有球呢？情况1：如果没有进行过操作二，那就只需要判断展开全文

来泡池子了的西红柿很奔放

发表于 2024-11-28 15:44:44

#include <stdio.h> #include <stdbool.h> int main() { int n, m; if (scanf("%d %d", &n, &m) != EOF) { int 展开全文

叫啥名

发表于 2025-05-23 12:10:31

// #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432 #include <iostream> #include <cstring> #include <vector> using n 展开全文

dopplerXD

发表于 2024-11-25 08:41:58

看到这个题第一眼没思路，第二眼直接上线段树区间修改，看了题解发现怪不得这题难度是简单[牛泪]最高赞题解妙啊[赞] #include <bits/stdc++.h> template<class T> struct Segt { struct node { 展开全文

问题信息

来自：2023年美团秋招编程...

难度：

15条回答 53收藏 2647浏览

小球投盒

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题