原题
思路
分析
我们先假设队伍如下：
| People | left hand | right hand |
|---|---|---|
| Before | \(S_a\) | |
| A | \(a_1\) | \(b_1\) |
| B | \(a_2\) | \(b_2\) |
| After | \(S_b\) |
现在我们要交换A、B，队伍如下：
| People | left hand | right hand |
|---|---|---|
| Before | \(S_a\) | |
| B | \(a_2\) | \(b_2\) |
| A | \(a_1\) | \(b_1\) |
| After | \(S_b\) |
我们可以发现：这样交换对于Before 和 After部分的结果没有影响，只对A 和 B 的部分结果有影响。
对于交换前的答案：
\(ans1=\max\{\dfrac{S_a}{b_1},\dfrac{S_a\times a_1}{b_2}\}\)
对于交换后的答案：
\(ans2=\max\{\dfrac{S_a}{b_2},\dfrac{S_a\times a_2}{b_1}\}\)
我们知道,这些数都是大于等于\(1\)的正整数,于是：
\(\dfrac{S_a\times a_1}{b_2} \ge \dfrac{S_a}{b_2}\)
\(\dfrac{S_a\times a_2}{b_1} \ge \dfrac{S_a}{b_1}\)
因此，当我们假定 \(ans1 < ans2\)时，一定是：
\(\dfrac{S_a\times a_1}{b_2} < \dfrac{S_a\times a_2}{b_1}\)
化简得：
\(a_1\times a_2 < b_1 \times b_2\)
算法
显然，此关系满足传递性，即当
\(a_1\times a_2 < b_1 \times b_2\)
\(b_1\times b_2 < c_1 \times c_2\)
有：
\(a_1\times a_2 < c_1 \times c_2\)
因此，我们可以贪心，只要按此规则排序，再统计答案即可,注意要高精
代码
压位高精：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
const int MAXN = 1010;
const int base = 10000;
int n;
struct people{
int x,y;
bool operator < (const people &b ) const {
return (ll)x * y < (ll)b.x * b.y;
}
}peo[MAXN];
struct bignum{//only mul ,comp ans so on
int a[1020],len;
bignum() {//初始化
memset(a,0,sizeof(a));
len = 1;
}
void resize(){//限制位数
len = 1010;
for(int i = len - 1;i >= 0;i--)
if( a[i] > 0 ) {
len = i + 1;
return;
}
len = 1;
}
bool operator < (const bignum &b) const{//比大小
if ( len != b.len) return len < b.len;
for(int i = len - 1 ;i >= 0 ;i--){
if(a[i] != b.a[i]) return a[i] < b.a[i];
}
return 0;
}
bignum operator * (const int &b) const{ //乘法（高精乘int）
bignum c;
for(int i = 0; i < len ;i++){
c.a[i] += a[i] * b;
if( c.a[i] >= base) {
c.a[i+1] += c.a[i]/base;
c.a[i] %= base;
}
}
c.resize();
return c;
}
bignum operator / (const int &b) const{//除法（高精除int）
ll temp = 0;
bignum c;
if( b == 0) {
printf("Error!");
return c;
}
for(int i = len -1;i >= 0;i--){
temp = temp * base + a[i];
if(temp >= b) {
c.a[i] = temp / b;
temp %= b;
}
}
c.resize();
return c;
}
void print (){//输出
resize();
printf("%d",a[len-1]);
if ( len > 1)
for(int i = len - 2;i >=0;i--){
printf("%04d",a[i]);
}
return;
}
};
int main (){
scanf("%d",&n);
for(int i = 0;i <= n;i++){
scanf("%d %d",&peo[i].x,&peo[i].y);
}
sort(peo+1,peo+n+1);
bignum ans,tot;
tot.a[0] = 1 ;
tot = tot * peo[0].x;
for(int i = 1;i <= n;i++){
bignum temp = tot / peo[i].y;
tot = tot * peo[i].x;
if( ans < temp ) ans = temp;
}
ans.print();
return 0;
}
反思总结
应该是太久没写压位高精了，打错了INF回，我有几个出错的地方：
- 在
resize()函数里未在最后设置len=1,导致数为0时len很大 -
resize()函数里面把return写成break;，导致每个被resize()的数的len=1 -
base可以去1e5但只取了1e4 -
print()函数里面输出记忆错误：
printf("%4d",a[i]);
显然，少了0
5. *函数里面写成了：
bignum operator * (const int &b) const{
bignum c;
for(int i = 0; i < len ;i++){
c.a[i] = a[i] * b;
if( c.a[i] >= base) {
c.a[i+1] += c.a[i]/base;
c.a[i] %= base;
}
}
c.resize();
return c;
}
总的来说，我也要多练习压位高精……