310088: CF1781B. Going to the Cinema
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Going to the Cinema
题意翻译
- **本题一个测试点内有多组测试数据**。 - 有 $n$ 个数 $a_1,a_2,\cdots,a_n$,求有多少 01 数组 $w_1,w_2,\cdots,w_n$ 使得 $\nexists i\in[1,n]$: - 若 $w_i=0$,$\sum\limits_{1\leq j\leq n,i\neq j}w_i\geq a_i$; - 若 $w_i=1$,$\sum\limits_{1\leq j\leq n,i\neq j}w_i<a_i$。 - $2\leq n,\sum n\leq2\times10^5$,$0\leq a_i<n$。题目描述
A company of $ n $ people is planning a visit to the cinema. Every person can either go to the cinema or not. That depends on how many other people will go. Specifically, every person $ i $ said: "I want to go to the cinema if and only if at least $ a_i $ other people will go, not counting myself". That means that person $ i $ will become sad if: - they go to the cinema, and strictly less than $ a_i $ other people go; or - they don't go to the cinema, and at least $ a_i $ other people go. In how many ways can a set of people going to the cinema be chosen so that nobody becomes sad?输入输出格式
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. Each test case consists of two lines. The first line contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of people in the company. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n - 1 $ ) — integers from peoples' claims. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print a single integer — the number of different ways to choose a set of people going to the cinema so that nobody becomes sad.
输入输出样例
输入样例 #1
4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3
输出样例 #1
2
1
3
2