国王游戏

那天_rqy大佬做了个课件(_rqy讲课做课件辣!),给我们讲了些东西,贪心啥的,一些基础知识和算法

然后要拿着这个课件去外面讲课

其中讲到贪心时就讲到这样一道题:

原题目

翻译:对于每个人有两个元素\(l\)和\(r\),给定一个指定人作为第一个,其他人排成一列,对于某个特定的人\(i\)(不含国van♂),其权值就是:

\(\frac{\prod\limits_{j=1}^{i-1} l_j}{r_i}\)

易知不同的排列顺序会有着不同的情况,现在求最大权值可能最小值

就是使最大值最小

一看这种题就要用二分

我不会

所以用贪心,其实二分做不了,这是_rqy说的并且因为我菜我不会证明

这道题因为涉及很多公式计算,看上去像是一道数学题

那就先用数学公式推导

举个例子

考虑这个队列只有两个人\(a_1\)和\(a_2\):

当\(a_1\)在前时,他们的权值分别是:

\(\frac{l_{king}}{r_{a_1}}\)

与

\(\frac{l_{king}*l_{a_1}}{r_{a_2}}\)

\(a_2\)在前时:

\(\frac{l_{king}}{r_{a_2}}\)

与

\(\frac{l_{king}*l_{a_2}}{r_{a_1}}\)

由题意得:

这题要取的权值应是最大值

所以公式应是这样的恶心:

\(max(max(\frac{l_{king}}{r_{a_1}},\frac{l_{king}*l_{a_1}}{r_{a_2}}),max(\frac{l_{king}}{r_{a_2}},\frac{l_{king}*l_{a_2}}{r_{a_1}}))\)

首先,国王的权值是两种情况都需要乘的,所以可以提出来,而两者的\(r\)亦是如此,,就是都乘上\(r_{a_1}*r_{a_2}\)

所以可变式为这样:

\(\frac{l_{king}}{r_{a_1} r_{a_2}}*max(max({r_{a_2}},{l_{a_1}}{r_{a_1}}),max({r_{a_1}},{l_{a_2}}{r_{a_2}}))\)

一看就知道绝对不可能选\(r_{a_1}\)和\(r_{a_2}\)

所以只根据\({l_{a_1}}{r_{a_1}}\)和\({l_{a_2}}{r_{a_2}}\)考虑

为了让\(ans\)取到最小值,要把其乘积从小到大排,并且在计算其权值时:

1.需要高精,

2.一边计算一遍取最大值,这样才能是\(ans\),注意最后一项不一定是\(ans\)

那么这仅是对两个人的情况进行讨论,经过思索发现这个排序原则可以利用到有\(n\)个大臣的状态

先考虑他们仍然相邻,那么前面大臣的乘积是可以当上面公式的\(l_{king}\)提出来,照样交换

然后经过老多次交换,可以像冒泡排序一样导致不相邻的交换

完成

想起博客这么短的原因是没贴代码:

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n; int ka,kb; struct node{ int a,b; }peo[1005]; inline bool cmp(const node &l,const node &r){ return l.a*l.b<r.a*r.b; } struct num{ int w[30005]; int size; num(){ memset(w,0,sizeof w); } }ans; num operator *(num c,const int &k){ int wei=0; c.size+=5; for(int i=1;i<=c.size;i++){ c.w[i]*=k; c.w[i]+=wei; wei=c.w[i]/10; c.w[i]%=10; } while(!c.w[c.size]) c.size--; return c; } num operator /(num c,const int &k){ num ans; ans.size=c.size; for(int i=c.size;i>=1;i--){ ans.w[i]=c.w[i]/k; c.w[i-1]+=(c.w[i]%k)*10; } while(!ans.w[ans.size]&&ans.size>0) ans.size--; return ans; } bool operator>(const num &l,const num &r){ if(l.size>r.size) return 1; for(int i=l.size;i>=1;i--){ if(l.w[i]>r.w[i]) return 1; else if(l.w[i]<r.w[i]) return 0; }return 0; } int main(){ scanf("%d",&n); scanf("%d%d",&ka,&kb); for(int i=1;i<=n;i++) scanf("%d%d",&peo[i].a,&peo[i].b); sort(peo+1,peo+1+n,cmp); int t=0; while(ka>0){ ans.w[++t]=ka; ka/=10; }ans.size=t; num out=ans; for(int i=1;i<=n;i++){ num now=ans/peo[i].b; if(now>out) out=now; ans=ans*peo[i].a; } for(int i=out.size;i>=1;i--) printf("%d",out.w[i]); if(out.size==0) printf("0"); return 0; }

转载于:https://www.cnblogs.com/648-233/p/11181746.html

相关资源：各显卡算力对照表！