Codeforces Round #764 (Div. 3) 1624C Division by Two and Permutation

Codeforces Round #764 (Div. 3) 1624C Division by Two and Permutation 题目描述（传送门）

题目翻译：

给你一个由n个正整数组成的数列a。你可以对其进行以下 *** 作。
在一次 *** 作中，你可以将任意元素ai替换成⌊ai /2⌋，即将ai除以2（向下取整），也可以说是“整除2”。
判断是否可以通过任意次（可能0次）上述 *** 作将原数列变成一个全排列（all permutation，即用整数1~n以任意顺序排列而成的数列，且每个整数只出现一次）。
比如，如果a=[1,8,25,2]，n=4，则答案是yes，你可以进行以下 *** 作：

将8替换成⌊8/2⌋=4，则a=[1,4,25,2]。将25替换成⌊25/2⌋=12，则a=[1,4,12,2]。将12替换成⌊12/2⌋=6，则a=[1,4,6,2]。将6替换成⌊6/2⌋=3，则a=[1,4,3,2]。

解题思路：

首先，如果结果是yes，则表示原队列中的所有元素可以通过“整除2”的 *** 作在全排列中“各司其职”。另外你可以发现，有些数字可以担任好多“职位”（但不能同时担任）。比如8和4，8可以担任8,4,2,1，而4只能担任4,2,1。这说明，数字越大，能担任的“职位”越多，而我应当尽可能地物尽其用，这似乎体现了“贪心”的思想。也就是说如果给我一个数字8，而我发现“职位8”还空着，那我应当优先让8担任“职位8”；如果“职位8”有数字占了，而“职位4”空着，那我应当优先让8担任“职位4”。而如果在“职位8”、“职位4”空着，其他的职位都已经被占了的情况下，我却让8担任“职位4”，那“职位8”就只能空着了，因为4没法担任“职位8”。体现在现实生活中就是，先把高要求的职位给落实了，低要求的职位后落实，即使没有正好对应低要求职位的职员，大不了用牛刀宰鸡。

代码：

#include
#include
using namespace std;
int main(){
//	freopen("1.txt","r",stdin);
	int t,n,a,book[60],cnt;
	cin>>t;
	while(t--){
		cin>>n;
		memset(book,0,sizeof(book));
		cnt=n;
		for(int i=0;i>a;
			while(a>0){
				if(a>=1&&a<=n&&book[a]==0){
					book[a]=1;
					cnt--;
					break;
				}
				a/=2;
			}
		}
		if(cnt==0) cout<<"YES"<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702769.html