首页 > 代码库 > 【洛谷P1080】国王游戏

【洛谷P1080】国王游戏

2024-08-18 08:05:31   220人阅读

我们按照左右手数的乘积升序排序，就能使最多金币数最小了

为什么呢？

我们知道：

1）如果相邻的两个人交换位置，只会影响到这两个人的值，不会影响他人

2）假设相邻的两个人i, i + 1。设A[i] B[i] <= A[i + 1] B[i + 1]，i之前所有人的左手乘积为S。

ans1 = max{S / B[i], S * A[i] / B[i + 1]}

ans2 = max{S / B[i + 1], S * A[i + 1] / B[i]}

因为，A[i] B[i] <= A[i + 1] B[i + 1]

所以，S A[i] / B[i + 1] <= S A[i + 1] / B[i]

又因为，S / B[i + 1] <= S * A[i] / B[i + 1]

所以，ans2 = S * A[i + 1] / B[i]

ans1 = max{S / B[i], S * A[i] / B[i + 1]（<=S A[i + 1] / B[i]）}

所以，ans1 <= ans2

至于高精度，，

这里粘的是60分代码，，自己YY一下就好

技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long 
 5 using namespace std;
 6 const int N=20010;
 7 ll s[N],tmp[N];
 8 struct fx{
 9     ll l,r,x;
10 }d[1010];
11 bool cmp(fx a,fx b){
12     return a.x<b.x;
13 }
14 int main(){
15     int n;
16     ll ans=0,p,q;
17     scanf("%d",&n);
18     for (int i=0;i<=n;i++){
19         scanf("%lld %lld",&d[i].l,&d[i].r);
20         d[i].x=d[i].l*d[i].r; 
21     }
22     sort(d+1,d+n+1,cmp);
23     p=1;
24     for (int i=1;i<=n;i++){
25         p*=d[i-1].l;
26         if (ans<p/d[i].r)
27             ans=p/d[i].r;
28     }
29     printf("%lld",ans);
30     return 0;
31 }
60

【洛谷P1080】国王游戏


联系
我们