程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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;
}





 

 

 

??

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved