QDU BelamiYao的一道简单签到题(思维)

109 阅读 0 评论 72 点赞

我是靠谱客的博主热情高山，这篇文章主要介绍QDU BelamiYao的一道简单签到题(思维)，现在分享给大家，希望可以做个参考。

BelamiYao的一道简单签到题

发布时间: 2017年6月11日 17:59 最后更新: 2017年6月15日 13:32 时间限制: 300ms 内存限制: 128M

描述BelamiYao得到了一个数列，但BelamiYao想把数列中所有的数都变成同一个数，然而BelamiYao只有两种nr4数字膜法，每一秒只能使用一种膜法
 
1.将一个数乘2.
2.将一个数除2，并向下取整。
BelamiYao想问你最少需要花费多少秒才能将数列中所有的数都变成同一个数。
输入 第一行一个整数n代表数列中数字的个数
 接下来n个整数。
 保证输入所有数据均小于100000
输出 输出一个整数代表答案
样例输入1  
  复制 
  复制代码3
4 8 23
4 8 2
样例输出1复制代码22

思路：这题时间给那么少，真心不敢过于暴力(估计时间少写个0)。只需要存储这组数最大值在除2的过程中的所有

的中间值*2^k然后进行枚举(所有可能能变成的值)即可。还有一个点是怎么判断这组数怎么以最小次数变成这个可

能值，这儿可能会想bfs，但是每次都会对标记数组进行memset，所以复杂度颇高。先进行能不能从a[i]变到当前

可能值得判断，不能直接break，能则只需要进行下面的运算便可求得最小次数，假如x->y，当x>y时，对x/2，当

y>x时，对y/2，直到x=y时的操作数便是所求。

Code:

复制代码

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <set>
using namespace std;
const int maxn = 100005;
const int inf = 0x3f3f3f3f;
int a[maxn], ans, up;
set<int> s;
set<int>::iterator it;
void add()
{
	int k = up;
	while(k > 1)
	{
		if(k/2*2 != k && k/2)
		{
			int kk = k/2*2;
			while(kk <= up)
			{
				s.insert(kk);
				kk <<= 1;
			}
		}
		s.insert(k);
		k >>= 1;
	}
	k = 1;
	while(k <= up)
	{
		s.insert(k);
		k <<= 1;
	}
}
int calc(int x, int y)
{
	int cnt = 0;
	while(x != y)
	{
		if(x > y) x /= 2;
		else y /= 2;
		++cnt;
	}
	return cnt;
}
int main()
{
	int n, k, flag, cnt, ej;
	scanf("%d", &n); up = 0;
	for(int i = 0; i < n; ++i)
	{
		scanf("%d", &a[i]);
		up = max(up, a[i]);
	}
	add(); ans = inf;
	for(it = s.begin(); it != s.end(); ++it)
	{
		ej = *it; cnt = 0; flag = 1;
		while(ej%2 == 0) ej /= 2;
		for(int i = 0; i < n; ++i)
		{
			int x = a[i];
			while(x%ej != 0) x /= 2;
			if(x == 0)
			{
				flag = 0;
				break;
			}
			else cnt += calc(a[i], *it);
		}
		if(flag) ans = min(ans, cnt);
	}
	printf("%dn", ans);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <set>
using namespace std;
const int maxn = 100005;
const int inf = 0x3f3f3f3f;
int a[maxn], ans, up;
set<int> s;
set<int>::iterator it;
void add()
{
	int k = up;
	while(k > 1)
	{
		if(k/2*2 != k && k/2)
		{
			int kk = k/2*2;
			while(kk <= up)
			{
				s.insert(kk);
				kk <<= 1;
			}
		}
		s.insert(k);
		k >>= 1;
	}
	k = 1;
	while(k <= up)
	{
		s.insert(k);
		k <<= 1;
	}
}
int calc(int x, int y)
{
	int cnt = 0;
	while(x != y)
	{
		if(x > y) x /= 2;
		else y /= 2;
		++cnt;
	}
	return cnt;
}
int main()
{
	int n, k, flag, cnt, ej;
	scanf("%d", &n); up = 0;
	for(int i = 0; i < n; ++i)
	{
		scanf("%d", &a[i]);
		up = max(up, a[i]);
	}
	add(); ans = inf;
	for(it = s.begin(); it != s.end(); ++it)
	{
		ej = *it; cnt = 0; flag = 1;
		while(ej%2 == 0) ej /= 2;
		for(int i = 0; i < n; ++i)
		{
			int x = a[i];
			while(x%ej != 0) x /= 2;
			if(x == 0)
			{
				flag = 0;
				break;
			}
			else cnt += calc(a[i], *it);
		}
		if(flag) ans = min(ans, cnt);
	}
	printf("%dn", ans);
	return 0;
}