POI #Year2012 #数学
贪心的每次选择最接近的两个数,\(x=min(x-fib_{i-1},fib_i-x)\)
// Author: xiaruize
const int N = 2e5 + 10;
vector<int> vec;
int n;
void solve()
{
int res = 0;
cin >> n;
while (n)
{
auto it = upper_bound(ALL(vec), n);
n = min(n - (*prev(it)), (*it) - n);
res++;
}
cout << res << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
vec.push_back(1);
vec.push_back(2);
while (vec[vec.size() - 1] + vec[vec.size() - 2] <= 1e18)
vec.push_back(vec[vec.size() - 1] + vec[vec.size() - 2]);
cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
标签:POI2012ROZ,min,int,res,fib,Fibonacci,Representation,vec
From: https://www.cnblogs.com/xiaruize/p/18156737