题目链接：https://www.luogu.com.cn/problem/P1080
这是一道贪心题，贪心的策略是将大臣们按左右手金币的乘积升序排列，具体证明过程可以参见洛谷大佬的题解，这里就不再赘述了。
因为本菜鸡之前没有接触过高精度运算，对C++的运算符重载也不太熟练，所以正好借此机会记录一下用到的高精度模版。模版框架参考于：https://blog.csdn.net/Wall_F/article/details/8373395
然而，直接复制该模版会导致TLE，原因在于这道题只需要高精度乘（除）低精度即可，但模版的乘除法运算是支持双高精度的，依赖于高精度的加减法，算法更加复杂，对于这道题来说增加了不必要的时间开销。所以我们需要把乘除法修改一下，删除高精度加减法的部分，得到如下简化版的代码，并顺利AC。
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
| #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 10010;
struct bign
{
int len, s[MAXN];
bign ()
{
memset(s, 0, sizeof(s));
len = 1;
}
bign (int num) { *this = num; }
bign (const char *num) { *this = num; }
bign operator = (const int num)
{
char s[MAXN];
sprintf(s, "%d", num);
*this = s;
return *this;
}
bign operator = (const char *num)
{
for(int i = 0; num[i] == '0'; num++);
len = strlen(num);
for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
return *this;
}
void clean()
{
while(len > 1 && !s[len-1]) len--;
}
bign operator * (const int &b)
{
bign c;
c.len = len + 5;
for(int i = 0; i < len; i++)
c.s[i] += s[i] * b;
for(int i = 0; i < c.len; i++)
{
c.s[i+1] += c.s[i]/10;
c.s[i] %= 10;
}
c.clean();
return c;
}
bign operator *= (const int &b)
{
*this = *this * b;
return *this;
}
bign operator / (const int &b)
{
bign c;
int f = 0;
for(int i = len-1; i >= 0; i--)
{
f = f*10 + s[i];
while(f >= b)
{
f -= b;
c.s[i]++;
}
}
c.len = len;
c.clean();
return c;
}
bign operator /= (const int &b)
{
*this = *this / b;
return *this;
}
bool operator < (const bign &b)
{
if(len != b.len) return len < b.len;
for(int i = len-1; i != -1; i--)
{
if(s[i] != b.s[i]) return s[i] < b.s[i];
}
return false;
}
bool operator > (const bign &b)
{
if(len != b.len) return len > b.len;
for(int i = len-1; i != -1; i--)
{
if(s[i] != b.s[i]) return s[i] > b.s[i];
}
return false;
}
bool operator == (const bign &b)
{
return !(*this > b) && !(*this < b);
}
bool operator >= (const bign &b)
{
return *this > b || *this == b;
}
string str() const
{
string res = "";
for(int i = 0; i < len; i++) res = char(s[i]+'0')+res;
return res;
}
};
istream& operator >> (istream &in, bign &x)
{
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream &out, const bign &x)
{
out << x.str();
return out;
}
struct Minister
{
int left, right;
};
bool cmp(Minister a, Minister b)
{
return a.left * a.right < b.left * b.right;
}
int main()
{
int n;
int kingLeft, kingRight;
cin >> n;
cin >> kingLeft >> kingRight;
vector<Minister> queue;
for (int i = 0; i < n; i++)
{
Minister m;
cin >> m.left >> m.right;
queue.push_back(m);
}
sort(queue.begin(), queue.end(), cmp);
bign reward, maxReward = 0;
bign product = kingLeft;
for (int i = 0; i < n; i++)
{
reward = product / queue[i].right;
if (reward >= maxReward)
maxReward = reward;
product *= queue[i].left;
}
cout << maxReward << endl;
return 0;
}
|