高精毒瘤题

考虑贪心。

对于两个大臣 \(i\) 和 \(j\)，当 \(a_i \times b_i <a_j \times b_j\) 时，\(i\) 排在 \(j\) 前更优 ### 证明： 因为所有大臣排成一列，所以我们考虑其中两个的关系，就可以推广到所有大臣。 我们还是取两个大臣 \(i\) 和 \(j\)，他们前面的人左手上的积为 \(x\)，假设 \(i\) 在前面更优，则有： \[ans_1=\max(\frac{x}{b_i},\frac{x\times a_i}{b_j})\] 若 \(j\) 在前面更优，则有 \[ans_2=\max(\frac{x}{b_j},\frac{x\times a_j}{b_i})\] 显然有 \[\frac{x}{b_i} \le \frac{x\times a_j}{b_i},\frac{x}{b_j}\le\frac{x\times a_i}{b_j}\] 若令 \(ans_1 < ans_2\)，则必然有 \[\frac{x\times a_i}{b_j}<\frac{x\times a_j}{b_i}\] 化简，得 \[a_i \times b_i < a_j \times b_j\] 证毕。

code:

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<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;
int n,a,b;
struct node{
	int a,b;
}e[N];
bool operator<(node x,node y){
	return x.a*x.b<y.a*y.b;
}
struct ll{
	int num[N*5];
	int len;
	ll(){
		memset(num,0,sizeof(num));
		len=0;
		return;
	}
	void operator=(int x){
		while(x){
			num[++len]=x%10;
			x/=10;
		}
		return;
	}
	bool operator<(const ll &x)const{
		if(this->len<x.len)
			return 1;
		if(this->len>x.len)
			return 0;
		for(int i=len;i;i--){
			if(this->num[i]<x.num[i])
				return 1;
			if(this->num[i]>x.num[i])
				return 0;
		}
		return 1;
	}
	ll operator*(const int &x)const{
		ll ans;
		ans.len=this->len;
		for(int i=1;i<=this->len;i++){
			ans.num[i]+=this->num[i]*x;
			ans.num[i+1]=ans.num[i]/10;
			ans.num[i]%=10;
		}
		if(ans.num[ans.len+1]){
			int k=ans.num[ans.len+1];
			while(k){
				ans.len++;
				ans.num[ans.len]=k%10;
				k/=10;
			}
		}
		return ans;
	}
	bool operator<(const int &x)const{
		int k=x,len1=0;
		while(k){
			k/=10;
			len1++;
		}
		if(len1>this->len)
			return 1;
		if(len1<this->len)
			return 0;
		k=x;
		for(int i=1;i<=n;i++){
			if(this->num[i]<k%10)
				return 1;
			if(this->num[i]>k%10)
				return 0;
			k/=10;
		}
		return 0;
	}
	ll operator/(const int &x)const{
		ll ans;
		if(*this<x)
			return ans;
		ans.len=this->len;
		int k=0;
		for(int i=this->len;i;i--){
			k=k*10+this->num[i];
			ans.num[i]=k/x;
			k%=x;
		}
		while(!ans.num[ans.len])
			ans.len--;
		return ans;
	}
};
void print(ll x){
	if(x.len==0){
		printf("0");
		return;
	}
	for(int i=x.len;i;i--)
		printf("%d",x.num[i]);
	return;
}
ll max1(ll x,ll y){
	if(x<y)
		return y;
	return x;
}
ll cnt,ans1;
int main(){
	scanf("%d%d%d",&n,&a,&b);
	cnt=a;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&e[i].a,&e[i].b);
	sort(e+1,e+1+n);
	for(int i=1;i<=n;i++){
		ans1=max1(ans1,cnt/e[i].b);
		cnt=cnt*e[i].a;
	}
	print(ans1);
	return 0;
}