程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Amr and Chemistry（數學+亂搞）

Codeforces Amr and Chemistry（數學+亂搞）

編輯：C++入門知識

Codeforces Amr and Chemistry（數學+亂搞）

題意：給n個數，每個數每次可以乘二或除以二（向下取整相當於左移或右移），問最少經過多少次操作可以使這n個數變相等。

思路：首先考慮每個數的可能取值，將一個數表示成s*2^k的形式，s是奇數。

那麼這個數的所有可能取值為s'*2^x,(s'=s/2,(s/2)/2,.....)且s'*2^x<=100000

因為這題數據范圍不大，而且每個值可能的取值不多最多幾百個，所以記錄1到100000每個值可能被取到的次數以及總操作數，最後從1遍歷到100000取最小的ans即可

ps：個人賽這道題做了一下午無數亂搞寫的代碼巨惡心......晚上回來優化了一下勉強能看..........

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  

//const int maxn = 100 + 5;
const int INF = 100000000;
int n, abc;
int vol[100010], ans[100010];  //vol代表每個容量可能被取到的次數，ans表示取到該容量所要的操作總數 
int main() {
//	freopen(input.txt, r, stdin);
	while(scanf(%d, &n) == 1) {
		memset(vol, 0, sizeof(vol));
		memset(ans, 0, sizeof(ans));
		for(int i = 0; i < n; i++) {
			cin >> abc;
			int t = abc;
			int cnt = 1, cnt1 = 0;
			abc <<= 1;
			while(abc <= 100000) {
				vol[abc]++;
				ans[abc] += cnt;
				cnt++;
				abc <<= 1;
			}
			cnt = 0;
			while(t%2 == 0) {
				vol[t]++;
				ans[t] += cnt;
				cnt++;
				cnt1++;
				t >>= 1;
			}
			vol[t]++;
			ans[t] += cnt;
			t >>= 1;
			cnt1++;
			while(t != 0) {
				int u = t;		
				int cnt2 = cnt1;
				while(u <= 100000) {
					vol[u]++;
					ans[u] += cnt2;
					cnt2++;
					u <<= 1;
				}
				if(t%2 == 0) {
					while(t%2 == 0) {
						t >>= 1; 
						cnt1++;
						vol[t]++;
						ans[t] += cnt1;
					}
				}
				t >>= 1; cnt1++;
			}
		}
		int pans = INF;
		for(int i = 0; i <= 100000; i++) if(vol[i] == n)
			pans = min(pans, ans[i]);
		//cout << vol[2] << endl << vol[1] << endl << vol[8] << endl;
		cout << pans << endl;	
	}
	return 0;
}