ZT26 小球投盒

描述

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

输入描述：

第一行两个整数 n 和 m，表示盒子的数量和操作的次数。
接下来 m 行，每行两个整数 ti​ 和 xi​，表示第 i 次操作的类型和 x 的值。
1≤n,m≤10^5
1≤ti​≤2
1≤xi​≤n

输出描述：

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

示例1

输入：

3 3
1 1
1 2
1 3

输出：

3

说明：

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

示例2

输入：

3 4
1 1
2 2
1 3
1 2

输出：

4

说明：

第一次操作后，盒子 1 里有小球。

第二次操作后，盒子 1、3、4 里有小球。

第三次操作后，盒子 1、3、4 里有小球。

第四次操作后，每个盒子里都有小球。

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.n个盒子，m次操作

2.每次操作有，ti和xi分别表示操作类型和x值

3.操作类型1：向编号为x的盒子放入一个小球

操作类型2：向编号不为x的所有盒子（n-1个）放入一个小球

4.小红想知道，第几次操作之后每个盒子都有小球

5.如果无法完成这个目标输出-1，可以输出操作次数

二、解题思路

1.定义一个数组dp[n]

2.全部值初始化为0

3.如果有操作1，那么将dp[t]设置为1

4.如果有操作2，那么将除了dp[t]之外的都设置为1

（如果dp[t] == 1那么直接返回当前操作次数）

5.设定一个opnums变量，记录操作次数，

6.设定一个count变量记录已经有多少盒子里有小球

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <stdbool.h>
int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != EOF) {
        int t, x, i;
        bool box[n + 1];
        for(i = 1; i <= n; i++) {
            box[i] = false;
        }
        int count = 0;
        int opnums = 0;
        for(i = 0; i < m; i++) {
            if(scanf("%d%d", &t, &x) != EOF) {
                opnums++;
                switch (t) {
                    case 1:
                        if(box[x] == false) {
                            box[x] = true;
                            count++;
                        }
                        break;
                    case 2:
                        if(box[x]) {
                            printf("%d\n", opnums);
                            return 0;
                        }
                        for(int j = 1; j < x; j++) {
                            box[j] = true;
                        }
                        for(int j = x + 1; j <= n; j++) {
                            box[j] = true;
                        }
                        count = n - 1;
                        break;
                }
                if(count == n) {
                    printf("%d\n", opnums);
                    return 0;
                }
            } else printf("error2\n");
        }
    } else printf("error\n");
    printf("-1\n");
    return 0;
}