Codeforces Round #764 (Div. 3) C. Division by Two and Permutation 题解(c++)

Codeforces Round #764 (Div. 3) C. Division by Two and Permutation 题解(c++),第1张

Codeforces Round #764 (Div. 3) C. Division by Two and Permutation 题解(c++) C. Division by Two and Permutation 【题目】

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].
[Input]

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"< 

感谢你的阅读(❁´◡`❁)

有错误欢迎指出,一起进步鸭!

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702479.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存