You are given an array a consisting of n positive integers. You can perform operations on it.
In one operation you can replace any element of the array ai with ⌊ai/2⌋, that is, by an integer part of dividing ai by 2 (rounding down).
See if you can apply the operation some number of times (possible 0) to make the array a become a permutation of numbers from 1 to n —that is, so that it contains all numbers from 1 to n, each exactly once.
For example, if a=[1,8,25,2], n=4, then the answer is yes. You could do the following:
- Replace 8 with ⌊8/2⌋=4, then a=[1,4,25,2].Replace 25 with ⌊25/2⌋=12, then a=[1,4,12,2].Replace 12 with ⌊12/2⌋=6, then a=[1,4,6,2].Replace 6 with ⌊6/2⌋=3, then a=[1,4,3,2].
The first line of input data contains an integer tt (1 ≤ t ≤ 10^4) —the number of test cases.
Each test case contains exactly two lines. The first one contains an integer nn (1 ≤ n ≤ 50), the second one contains integers a1,a2,…,an (1 ≤ ai ≤ 10^9).
[Output]For each test case, output on a separate line:
YES if you can make the array a become a permutation of numbers from 1 to n,NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).
【样例】 [Input]6 4 1 8 25 2 2 1 1 9 9 8 3 4 2 7 1 5 6 3 8 2 1 4 24 7 16 7 5 22 6 22 4 22[Output]
YES NO YES NO NO YES[Note]
The first test case is explained in the text of the problem statement.
In the second test case, it is not possible to get a permutation.
【思路】 解题的两个重点:1. a[i] 需除以2的条件(循环的条件):
输入的数 a[i] > n满足条件 a[i] <= n ,但 a[i] 重复出现
(直至 a[i] 在区间 [1,n] 内,循环结束)
2. 什么样的数据会出现结果“NO”?
当 a[i] 经过除以2的 *** 作后变成 0 ,数组a必不能成为1到n的数字的排列组合。
【核心代码】for (int i=1;i<=n;i++) { //遍历输入的数据 while (a[i]>n||flag[a[i]]==1) { //注意两判断条件的顺序 a[i]/=2; } if (a[i]==0) { //当数据中出现 0 时,数组a必不能成为1到n的数字的排列组合 break; } flag[a[i]]=1; //记录符合条件的a[i]是否已经出现 }【注意】
循环中的判断条件 “a[i] > n” 与 “flag[a[i]] == 1” 不可对调,否则会数组越界(Runtime error)。
因为我们开的flag数组大小是55,而题目中的数据a[i]最大可以是1*10^9。
应该先判断a[i]是否大于n,若a[i]<=n,再继续用flag数组判断这个数是否已经存在。
正确的顺序:
错误的顺序:
【完整AC代码】#include#include #include #define ll long long using namespace std; ll a[55],flag[55]; //flag--实现记录功能 int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while (t--) { memset(flag,0,sizeof(flag)); int n; cin>>n; int node=1; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++) { while (a[i]>n||flag[a[i]]==1) { //两判断条件不可对调 a[i]/=2; } if (a[i]==0) { node=0; break; } flag[a[i]]=1; } if (node) cout<<"YES"< 感谢你的阅读(❁´◡`❁)
有错误欢迎指出,一起进步鸭!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)