题意

有n个盒子，可以进行m次操作，每次操作有2种

• 向编号为x的盒子里放一个小球
• 向除了编号x的其他n-1个盒子里放一个小球

求第几次操作后，所有盒子里至少都有一个小球

思路

答案是具有单调性的，因为每次都是往盒子里放小球，第x次操作后，所有的盒子里至少有一个小球的话，那么第x+1操作后，也肯定满足这个条件。而且这个操作的顺序是不会改变的，可以二分答案的方式做。

对于二分的check函数，实际上就是判断执行了前mid次操作后，每个盒子里球的个数是否都大于0，操作1和操作2都可以看成对区间的操作，所以可以用差分数组来维护盒子里球的个数，最后求和后判断是否所有的盒子球的个数都大于0就可以知道执行前mid操作能否满足题意

时间复杂度nlogn

Go代码

package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	t, x := make([]int, m+1), make([]int, m+1)
	for i := 1; i <= m; i++ {
		fmt.Scan(&t[i], &x[i])
	}
	l, r := 1, m
	check := func(idx int) bool {
		sum := make([]int, n+1)
		for i := 1; i <= idx; i++ {
			if t[i] == 1 {
				sum[x[i]]++
				if x[i] + 1 <= n {
					sum[x[i]+1]--
				}
			} else {
				//[1,x-1] [x+1,n]
				sum[1]++
				sum[x[i]]-- //x[i]-1+1
				if x[i] + 1 <= n {
					sum[x[i]+1]++
				}
				//sum[n+1]--
			}
		}
		for i := 1; i <= n; i++ {
			sum[i] += sum[i-1]
			if sum[i] == 0 {
				return false
			}
		}
		return true
	}
	ans := -1
	for l <= r {
		mid := (l + r + 1) / 2
		if check(mid) {
			//还可以更少
			r = mid - 1
			ans = mid
		} else {
			l = mid + 1
		}
	}
	fmt.Println(ans)
}