题面
这是一个比较经典(害人不浅)的题目啊, 很早就听说过这个题目的大名, 今日得见, 果然非凡题所可以比拟的啊, 行了, 瞎扯就先扯到这里, 题目大意应该是很好解释的, 我就不解释了, 要使得最大值最小啊, 我们第一个想到的肯定是二分啊, 但是这题不用二分(我也不知道为啥, 反正看到就知道不用二分). 要问比二分更好的策略是什么, 肯定是贪心了, 那么这道题就考虑贪心吧. 因为最大值最小, 我们可以从最后一个向前分析, 毕竟最后一个的值最大是概率最大的情况, 不妨设当前考虑的最后一个人位置为(k), 设前面(k - 1)个人左手的乘积为(max(k - 1)), 每个人左手的数为(l[i]), 右手的数为(r[i])则有这样一个算式:
[frac{max(k - 1)}{r[k]} = frac{max(k - 1) * l[k]}{r[k] * l[k]}
]
观察到, 由于k为最后一个数, 故(max(k - 1))与(l[k])的乘积是一个定值, 所以, 只要(r[k] * l[k])的值最小就可以了, 然后假装选完了最后一个数, 选倒数第二个数, 此时倒数第二个数为除了最后一个数之外的最后一个数, 不停地往前选择, 最后会发现, 排队的方式就是按(l[i] * r[i])的大小升序排序, 所以就可以做完了, 多好啊...
具体实现
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 20005
using namespace std;
int n, L, R;
struct node
{
int l, r;
} per[N];
int sum[N], ans[N], num[N], cnt, tot, rnt;
inline int read()
{
int x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * w;
}
inline bool cmp(node a, node b) { return 1ll * a.l * a.r < 1ll * b.l * b.r; }
inline int gett(int x)
{
if(!x) return 1;
int res = 0;
while(x)
{
res++;
x /= 10;
}
return res;
}guowangyouxi
inline void times(int x)
{
bool flag = 0;
for(int i = cnt; i >= 0; i--)
{
sum[i] *= x;
int up = sum[i] / 10000;
sum[i] %= 10000;
if(up > 0)
{
if(i == cnt) { sum[cnt + 1] += up; flag = 1; }
else sum[i + 1] += up;
}
}
if(flag) cnt++;
}
inline void divite(int x)
{
int rem = 0; rnt = cnt;
for(int i = cnt; i >= 0; i--)
{
num[i] = (rem * 10000 + sum[i]) / x;
rem = (rem * 10000 + sum[i]) % x;
}
while(!num[rnt]) rnt--;
}
inline bool compare()
{
if(rnt > tot) return 1;
if(rnt < tot) return 0;
for(int i = rnt; i >= 0; i--)
{
if(num[i] > ans[i]) return 1;
if(num[i] == ans[i]) continue;
if(num[i] < ans[i]) return 0;
}
}
inline void cp()
{
tot = rnt;
for(int i = 0; i <= tot; i++) ans[i] = num[i];
}
int main()
{
n = read(); L = read(); R = read();
for(int i = 1; i <= n; i++) { per[i].l = read(); per[i].r = read(); }
sort(per + 1, per + n + 1, cmp);
sum[0] = L;
for(int i = 1; i <= n; i++)
{
divite(per[i].r);
times(per[i].l);
if(compare()) cp();
}
for(int i = tot; i >= 0; i--)
{
int number = 4 - gett(ans[i]);
if(i != tot) for(int j = 1; j <= number; j++) printf("0");
printf("%d", ans[i]);
}
puts("");
return 0;
}
其实我是拒绝写高精度的, 因为初学OI的时候给我带了一些极其不好的感受, 但写完这个题后, 啊, 高精似乎也不是很难啊......