两个难点。
- 怎么想到的贪心？
首先确定算法：
显然不是数据结构题。转成图论也不太可能。
考虑DP：f[i][j]表示前i个人取j状态的最小最大值......2^1000，直接放弃。
因为出现了“最大值最小”，考虑二分答案：如果我们有一个ans是最大值，我们怎么判断是否可行？
要确保每一个数都不会超过ans，这很困难。
思路戛然而止。
然后思考：本题要求排序。zbtrs:排序不就是贪心吗？
然后想到邻位互换法，得出贪心策略。
显然很难想出贪心来......
- 高精度
这个没什么好说的，写个高精度乘单精度，除单精度，比较大小，输出，就行了。
跑的十分之快，136ms十个点
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int N = ;
struct LL {
string num;
void out() {
for(int i = ; i < num.size(); i++) {
putchar(num[i]);
}
return;
}
LL operator * (const int& x) const {
int len = num.size();
int a[len + ];
memset(a, , sizeof(a));
for(int i = ; i < len; i++) {
a[i] = num[len - i - ] - '';
a[i] *= x;
}
for(int i = ; i < len; i++) {
if(a[i] > ) {
a[i + ] += a[i] / ;
a[i] %= ;
if(i + == len) {
len++;
}
}
}
string f = "";
for(int i = len - ; i >= ; i--) {
f += (a[i] + '');
}
LL t;
t.num = f;
return t;
}
LL operator / (const int x) const {
int len = num.size();
int a[len];
for(int i = ; i < len; i++) {
a[i] = num[len - i - ] - '';
}
for(int i = len - ; i > ; i--) {
a[i - ] += * (a[i] % x);
a[i] /= x;
}
a[] /= x;
while(len >= && a[len - ] == ) {
len--;
}
string f = "";
for(int i = len - ; i >= ; i--) {
f += (a[i] + '');
}
LL t;
t.num = f;
return t;
}
bool operator < (const LL& x) const {
if(num.size() != x.num.size()) {
return num.size() < x.num.size();
}
for(int i = ; i < num.size(); i++) {
if(num[i] != x.num[i]) {
return num[i] < x.num[i];
}
}
return ;
}
};
struct Man {
int a, b, c;
bool operator < (const Man &f) const{
return this->c < f.c;
}
}man[N];
int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d%d", &man[i].a, &man[i].b);
man[i].c = man[i].a * man[i].b;
} sort(man + , man + n + );
/*
for(int i = 1; i <= n; i++) {
printf("%d %d %d\n", man[i].a, man[i].b, man[i].c);
}
printf("\n");
*/
LL ans, now;
now.num = "";
ans.num = "";
for(int i = ; i < n; i++) {
now = now * man[i].a;
LL t = now / man[i + ].b;
if(ans < t) {
ans = t;
}
}
ans.out();
return ;
}
/**
3
1 7
6 1
2 3
2 3
ans:4
*/
AC代码