链接:
http://codeforces.com/contest/722/problem/D
题意
一个数x,可以变成2x,或者变成2x+1,可以变化若干次
现在给你n个不同的数Y,你需要找到n个不同的x,使得这n个不同的x经过变化之后,能够得到Y数组,你要使得最初的最大值最小。
问你应该怎么做。
题解:
贪心,每次选择最大的数,然后使得最大数变小即可,能变就变,用一个set去维护就好了。
代码:
1 #include<iostream> 2 #include<set> 3 using namespace std; 4 set<int> ms; 5 6 int main() 7 { 8 int n; 9 cin >> n; 10 for (int i = 1; i <= n; i++){ 11 int x; 12 cin >> x; 13 ms.insert(x); 14 } 15 while (1){ 16 int x = *--ms.end(); 17 int t = x; 18 x /= 2; 19 while (x) { 20 if (ms.find(x) == ms.end()) { 21 ms.erase(t); 22 ms.insert(x); 23 break; 24 } 25 x /= 2; 26 } 27 if (x == 0) break; 28 } 29 for (auto it = ms.begin(); it != ms.end(); it++) 30 cout << *it << " "; 31 cout << endl; 32 return 0; 33 }