题意:给定一个数列,每次操作只能将某个数乘以2或者除以2(向下取整)。求最小的操作次数使得所有的数都变为相同值。
比赛的时候最后没实现。唉,之后才A掉。开始一直在想二分次数,但是半天想不出怎么判断。后来发现其实每个数都能变成的数很少很少(最多400个不到),于是想到用数学方法+一点暴力,可惜时间不够了。
也不能完全算是数论题。只是用到了一些数学思想。需要一点预处理,后面的计算中还会用到二分的技巧。
对某个数n,设n = s*2^r(其中s为奇数),则n能变成这样一些数:s*2^k(k = 0,1,2 ...... )以及s能变成的更小的数。s能变成的数有s/2,设s/2 = s‘*2^r‘,则还能变成s‘*2^k(k = 0,1,2 ...... )以及s‘能变成的更小的数 ...... 以此类推下去。于是我们可以注意到这样一个情况:如果一个数a能变成数n,那么数a一定可以变成数s。反之,若一个数不能变成数s,那么它一定不能变成数n。进一步,如果两个数a,b都能变成n,那么a和b一定都能变成s。所以,我们可以先求出这个s,即所有的数都能变成s。注意,因为s是奇数,所以每个数变成s只能是不断除以2(向下取整)的结果。而且,我们至少可以求出一个这样的s出来——s = 1。这是显然的。所以为了使操作次数更少,我们取s中最大的(当然并不一定最优)。但是显然,所有的数必须都要可以变成这个数,那是肯定的。也就是说,大于这个数的奇数,都无法变到了。既然这样,那么可以作为最后都变成的候选的数只能是s以及s*2^k(k = 0,1,2 ...... )于是我们枚举k的值,计算每个数变成s*2^k需要的次数再相加,更新最小值即可。
求s有点类似于求所有的数的“最大公约数”这样的意思。只是这里是求x和y都能变到的最大的奇数而已。也是用递归求:如果x比y的两倍大,那么x/=2,如果y比x的两倍大,那么y/=2,否则x和y同时除以2,直到x和y相等,即得到了共同的能变成的最大的奇数。
s解决了,第二个问题是如何快速求一个数变成另一个数所需要的次数。这里用了一点小技巧,可以直接预处理后以近乎O(1)的复杂度求出。
首先定义一个数组base[i] 、base[i]满足i = base[i]*2^r(其实basi[i]就是上面所说的s),显然,对于奇数有base[i] = i,对于偶数有base[i] = base[i/2]。接下来就是计算cal(i, j) = 将 i 变成 j 需要的步数。可以发现,只要将 i 不断除以2直到base[i] = base[j]为止,此时的 i 和 j 只是差了2的幂的倍数,那么还需要操作这个幂值的次数即可将 i 变为 j。而这个幂值就等于log2(max(i,j)/min(i,j))。于是我们只需要求将 i 变为一个base值等于base[j]的数最少要除以多少次2。当然直接算也可以,就不断除以2直到base值等于base[j]为止。但是外层已经用去了n*log(n)复杂度,于是这里我们再对除以2的次数进行2分。一个数最大10W,最多也就能除以16次2。所以二分的复杂度是log2(16) = 4几乎就等于O(1)了。能进行二分是因为,若 i 数除以2^k后得到base值比base[j]更小,那么除以大于2^k的值一定更不会得到base[i]了。反之,i 除以2^k后得到的base值若比base[j]大,则它还要继续除以2。具有单调性,所以可以二分。于是cal(i,j) = 二分出来的幂值+(int)log2(max(i, j)/min(i, j));
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <stack> #include <queue> #include <vector> #include <map> using namespace std; const int MAX = 100005; const int INF = MAX*20; int base[MAX]; int n, a[MAX]; void initial() //预处理base数组 { for(int i = 1; i <= 100000; i++) { if(i%2) base[i] = i; else base[i] = base[i/2]; } } int getbase(int x, int y) //递归求两个数能同时变成的最大的奇数 { if(x == y) return x; if(x >> 1 >= y) return getbase(x >> 1, y); if(x << 1 <= y) return getbase(x, y >> 1); return getbase(x >> 1, y >> 1); } int cal(int x, int y) //求将x变成y所需要的步数 { int l = 0, r = 20, mid; while(l < r) { mid = (l + r) >> 1; if(base[x >> mid] > base[y]) l = mid + 1; else r = mid; } x >>= l; return l + (int)log2(max(x, y)/min(x, y)); } void input() { for(int i = 0; i < n; i++) scanf("%d", &a[i]); } void solve() { int all_base = a[0]; for(int i = 1; i < n; i++) all_base = getbase(all_base, a[i]); //先求出所有数都能变成的最大奇数all_base int ans = INF, number = all_base; while(number <= 100000) //枚举all_base的倍数作为最后变成的数,计算并更新 { int sum = 0; for(int i = 0; i < n; i++) sum += cal(a[i], number); ans = min(ans, sum); number <<= 1; } printf("%d\n", ans); } int main() { initial(); while(scanf("%d", &n) != EOF) { input(); solve(); } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
Codeforces 558C Amr and Chemistry 全都变相等
原文:http://blog.csdn.net/firstlucker/article/details/46888253