Dr. Evil Underscores
思路：對每位二進制進行判斷，如果當前位的二進制都為0或者1，則這個位對答案貢獻為0，如果當前為有0有1則這個位對答案貢獻(1 << bit)，然后對當前位為0和為1的分成兩個集合進行分治，所有答案取min，
1 #include <cstdio> 2 #include <iostream> 3 #include <cstdio> 4 #include <algorithm> 5 #include <functional> 6 #include <set> 7 #include <vector> 8 #include <queue> 9 #include <cstring> 10 #include <stack> 11 #include <climits> 12 13 using namespace std; 14 15 #define ll long long 16 #define pb push_back 17 #define fi first 18 #define se second 19 20 int process(int b, vector<int >& v){ 21 if(b < 0) return 0; 22 vector<int > v0, v1; 23 for(auto x : v){ 24 if((x >> b) & 1) v1.pb(x); 25 else v0.pb(x); 26 } 27 if(v0.size() == 0) return process(b - 1, v1); 28 if(v1.size() == 0) return process(b - 1, v0); 29 return min(process(b - 1, v0), process(b - 1, v1)) + (1 << b); 30 } 31 32 void solve(){ 33 34 int n; 35 cin >> n; 36 vector<int > a(n); 37 for(auto& in : a) cin >> in; 38 int ans = process(30, a); 39 cout << ans << endl; 40 } 41 42 int main(){ 43 44 // freopen("C:\\Users\\admin\\Desktop\\input.txt", "r", stdin); 45 // freopen("C:\\Users\\admin\\Desktop\\output.txt", "w", stdout); 46 ios::sync_with_stdio(false); 47 cin.tie(0); 48 cout.tie(0); 49 solve(); 50 51 return 0; 52 } 53
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53372.html
標籤：其他
上一篇：快排演算法的一點思考