这题不好写，一个问题在贪心怎么排序，再有的难点就是高精乘/除，都不好写。。
这次正经的写了个高精度乘/除。。留下来备用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include<iostream> #include<string> #include<algorithm> using namespace std; int n; struct bigInt { //For Non-negative Numbers private: string v; static string & bIsort(string & v) { //each char has reduced '0' for (int i = 0; i < v.length(); i++) { if (v[i] > 9) { if (i == v.length() - 1)v.append(1, v[i] / 10); else v[i + 1] += v[i] / 10; v[i] %= 10; } } return v; } static string lng2str(long long v) { string s = ""; while (v) { s.append(1, v % 10 + '0'); v /= 10; } reverse(s.begin(), s.end()); return s; } static string& trimPre0(string& v3) { while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin()); if (v3.length() == 0)v3 = "0"; return v3; } public: bigInt() { v = "0"; } bigInt(long long n) { v = lng2str(n); } bigInt(string s) { v = s; } bigInt& operator = (const bigInt & bI) { this->v = bI.v; return *this; } bigInt operator * (bigInt bI2) const { string v1 = v, v2 = bI2.v; if (v2.length() > v1.length())swap(v1, v2); reverse(v1.begin(), v1.end()); reverse(v2.begin(), v2.end()); string v3 = ""; for (int i = 0; i < v1.length(); i++)v1[i] -= '0'; for (int i = 0; i < v2.length(); i++)v2[i] -= '0'; v3.resize(v1.length() + v2.length(), 0); for (int i = 0; i < v2.length(); i++) { for (int j = 0; j < v1.length(); j++) { v3[i + j] += v2[i] * v1[j]; } bIsort(v3); } for (int i = 0; i < v3.length(); i++)v3[i] += '0'; reverse(v3.begin(), v3.end()); trimPre0(v3); return bigInt(v3); } bigInt operator / (long long bI2) const { string v1 = v; for (int i = 0; i < v1.length(); i++)v1[i] -= '0'; long long v2 = bI2; string v3 = ""; long long div = 0; for (int i = 0; i < v1.length(); i++) { div *= 10; div += v1[i]; if (div < v2) { v3.append(1, '0'); continue; } v3.append(lng2str(div / v2)); div %= v2; } return bigInt(trimPre0(v3)); } bool operator < (bigInt bI2) const { if (v.length() != bI2.v.length())return v.length() < bI2.v.length(); for (int i = 0; i < v.length(); i++) { if (v[i] != bI2.v[i])return v[i] < bI2.v[i]; } return false; } friend istream& operator >> (istream& in, bigInt& bI) { in >> bI.v; return in; } friend ostream& operator << (ostream& out, bigInt& bI) { out << bI.v; return out; } }; struct p { bigInt a; int b; bool operator < (const p& p2) { return a * b < p2.a*p2.b; } }ps[1005]; int main() { cin >> n; for (int i = 1; i <= n + 1; i++) { cin >> ps[i].a >> ps[i].b; } sort(ps + 2, ps + n + 2); bigInt multiply = ps[1].a; bigInt mmax("0"); for (int i = 2; i <= n + 1; i++) { mmax = max(mmax, multiply / ps[i].b); multiply =multiply* ps[i].a; } cout << mmax; } |