程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11714 - Blind Sorting(推理貪心)

UVA 11714 - Blind Sorting(推理貪心)

編輯:C++入門知識

I I U P C 2 0 0 9

Problem B: Blind Sorting

I am a polar bear. But I am not just an ordinary polar bear. Yes I am extra ordinary! I love to play with numbers. One day my very good friend Mr. Panda came to me, and challenged me to solve a puzzle. He blindfolded me, and said that I have n distinct numbers. What I can ask is whether a’th number is larger than b’th number and he will answer me properly. What I have to do is to find out the largest and second largest number. I thought for a while and said “Come on, I will do it in minimum number of comparison.”

Input

There will be a non-negative integer, n in each of the line of input where n is as described above. n will be less than any 10 digit prime number and not less than the smallest prime.

Output

For each n, output number of questions that I have to ask Mr. Panda in the worst case.

Sample Input

Output for Sample Input

2

4

1

4


題意:有n個不同的數,你可以詢問a,b哪個大,會得到答案,然後問最少要幾次保證能挑選出最大和第二大的數。

思路:n個數,先以打擂台的方式,兩兩比較出最大的,n - 1次,然後在由被最大PK下去的數字中,比較出最大的,有log(n)個數,需要進行log(n) - 1次,注意是向上取整。

代碼:

#include 
#include 
#include 

int n;

int main() {
	while (~scanf("%d", &n)) {
		printf("%d\n", n - 1 + (int)(ceil(log(n)/log(2)) + 1e-9) - 1);
	}
	return 0;
}


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