給定的問題是：給出了多個自然數“N”。操作 half 減去集合中最大的元素，將它分成兩個相等的部分，然后將兩個結果數回傳給集合。任務是在應用“n”次半運算時找到集合中的最大數。
輸入格式
對于標準輸入的每個例子都給出：“N”是集合中數字的個數，以及多個“n”的元素；
約束
0<= N <= 100 0<=n <= 2000000
輸出：分數或整數。
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
class Fraction{
public:
Fraction(int t) : top(t), bottom(1) {}
Fraction(int t, int b) : top(t), bottom(b)
{
normalize();
}
int numerator() const
{
return top;
}
int denominator() const
{
return bottom;
}
int compare(const Fraction& right) const
{
return numerator() * right.denominator() - denominator() * right.numerator();
}
private:
void normalize()
{
int sign = 1;
if(top < 0)
{
sign = -1;
top = -top;
}
if(bottom < 0)
{
sign = -1;
bottom = -bottom;
}
assert(bottom != 0);
int d = 1;
if(top > 0) d = gcd(top, bottom);
top = sign *(top / d);
bottom = bottom / d;
}
int gcd(int n, int m)
{
assert(n > 0 && m > 0);
while(n!=m)
{
if(n < m)
m -= n;
else
n -= m;
}
return n;
}
int top;
int bottom;
};
Fraction operator/(const Fraction& left, const Fraction& right)
{
Fraction result(left.numerator() * right.denominator(),
left.denominator() * right.numerator());
return result;
}
bool operator<(const Fraction& left, const Fraction& right)
{
return left.compare(right) < 0;
}
ostream& operator<<(ostream& out, const Fraction& value)
{
if(value.denominator() != 1)
out << value.numerator() << "/" << value.denominator();
else
out << value.numerator();
return out;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,n;
while(cin >> N && cin >> n)
{
vector<Fraction> vec;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
vec.push_back(value);
}
for(int i = 0; i < n; i )
{
Fraction temp = *max_element(vec.begin(), vec.end()) / 2;
int maxIndex = distance(vec.begin(), max_element(vec.begin(), vec.end()));
vec[maxIndex] = temp;
vec.push_back(temp);
}
cout << *max_element(vec.begin(), vec.end())<< endl;
}
return 0;
}
該代碼確實有效，但我的問題是它因hackerrank超時而終止我也嘗試對其進行排序并處理最后一個元素，但它甚至比max_element還要慢。我正在尋找一種優化我的代碼的方法或一種完全不同的方法的想法。
這里也有 make_heap 的實作，但它經歷了 800 次迭代，它讓我超時（應該能夠處理 2000000）
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,n;
while(cin >> N && cin >> n)
{
vector<Fraction> vec;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
vec.push_back(value);
}
make_heap(vec.begin(),vec.end());
for(int i = 0; i < n; i )
{
cout << "was here: " << i << endl;
vec.push_back(vec.front() / 2); push_heap(vec.begin(),vec.end());
vec.push_back(vec.front() / 2); push_heap(vec.begin(),vec.end());
pop_heap(vec.begin(),vec.end()); vec.pop_back();
}
cout<< vec.front() << '\n';
}
return 0;
}
也用priority_queue試過了，它在由于超時而終止之前也正好有736次迭代
int main() {
int N,n;
while(cin >> N && cin >> n)
{
priority_queue<Fraction> frac;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
frac.push(value);
}
for(int i = 0; i < n; i )
{
Fraction temp = frac.top() / 2;
frac.pop();
frac.push(temp);
frac.push(temp);
}
cout << frac.top() << endl;
}
return 0;
}
如果有人想知道這是解決方案：
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,n;
while(cin >> N && cin >> n)
{
vector<pair<Fraction, int>> vec;
for(int i = 0; i < N; i )
{
int value;
cin >> value;
vec.push_back(make_pair(value,1));
}
sort(vec.begin(),vec.end());
while(vec.back().second <= n)
{
n -= vec.back().second;
pair<Fraction,int> temp(vec.back().first / 2, vec.back().second * 2);
vec.pop_back();
vec.push_back(temp);
sort(vec.begin(),vec.end());
}
cout << vec.back().first << endl;
}
return 0;
}
uj5u.com熱心網友回復：
你需要的技巧是你不需要列出所有的數字，你只需要有數量和數量。
那不是使用 a Fraction，而是使用 a std::pair<Fraction, int>。關鍵回圈變成如下偽代碼
while (count of top element < n)
{
n -= count of top element
temp = (value of top element / 2, count of top element * 2)
remove top element
push temp
}
目前，在每次回圈迭代中，您只需執行一個步驟并擴展您的資料結構。但是使用這種方法，每次回圈迭代都會執行許多步驟，并且資料結構永遠不會改變大小。
你最壞的情況是 ifN = 100和n = 2000000。然后你最終不得不經歷回圈2000000時間并擁有一個包含2000100 Fraction物件的資料結構。
通過這種改進，回圈的前 100 次執行 100 步，接下來的 100 次執行 200 步，接下來的 100 次執行 400 步，依此類推。結果是在 100k 回圈中您執行 (2^k-1) * 100 步。所以在 1500 次回圈中你已經完成了超過 200 萬步，但你仍然只有 100 對資料。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387602.html
上一篇：用int對char求和的C程式