[NOIP2012TG] 洛谷 P1080 国王游戏

阳光穿透心脏的1/2处 2023-08-17 17:49 127阅读 0赞

### 题意 ###

给定两个等长序列\\(a\[n\],b\[n\]\\)，与整数\\(a,b\\)。通过调换位置使

\\\[\\max\_\{i=1\}^\{n\}\{\\biggl\\lfloor\\frac\{(a\\times\\prod\_\{j=1\}^\{i-1\}a\_i)\}\{b\_i\}\\biggr\\rfloor\}\\quad (\\forall a\_i,\\forall b\_i \\in\\mathbb\{N+\})\\\]

最小。

### 分析 ###

从`重新安排顺序`容易看出，要求进行排序。这就要求我们用贪心思想分析题目，找到贪心的标准。

由冒泡排序的知识，容易得到**邻项交换可使序列有序。**  
并且冒泡排序与快速排序效果相同，直接sort后求解即可。

所以我们利用贪心的常见思路：**考虑只有两个元素的情况**。当然，列式表达第i项与第i+1项效果相同，只是不便书写。

也就是说，两个元素\\(i,j\\quad(j=i+1)\\)的大小关系可以拓展到任意\\(i,j\\quad(i<j)\\)

### 引理 ###

当\\(x>0\\)时：

*  \\(\\max(a,b)\\times x=\\max(ax,bx)\\)

非常易证。

### 证明 ###

设元素分别为\\((a1,b1),(a2,b2)\\)，奖金分别为\\(m,n\\)，有

\\\[m=\\frac\{a\}\{b\_1\}\\\]

\\\[n=\\frac\{a\\times a\_1\}\{b\_2\}\\\]

交换后为

\\\[m'=\\frac\{a\}\{b\_2\}\\\]

\\\[n'=\\frac\{a\\times a\_2\}\{b\_1\}\\\]

需要交换的条件是

\\\[\\max(m,n)>\\max(m',n')\\\]

代入有

\\\[\\max(\\frac\{a\}\{b\_1\},\\frac\{a\\times a\_1\}\{b\_2\})>\\max(\\frac\{a\}\{b\_2\},\\frac\{a\\times a\_2\}\{b\_1\})\\\]

### 进一步化简 ###

可有可无

两边同时乘\\(\\frac\{b\_1b\_2\}\{a\}\\)

\\\[\\max(b\_2,a\_1b\_1)>\\max(b\_1,a\_2b\_2)\\\]

*  当\\(b\_2<a\_1b\_1,b\_1<a\_2b\_2\\)时  
    ，直接比较\\(a\_1b\_1,a\_2b\_2\\)大小
 *  当\\(b\_2>a\_1b\_1,b\_1<a\_2b\_2\\)时  
    ，必有\\(a\_1b\_1<b\_2<a\_2b\_2\\)，等同于直接比较\\(a\_1b\_1,a\_2b\_2\\)
 *  当\\(b\_2<a\_1b\_1,b\_1>a\_2b\_2\\)时  
    ，同上
 *  当\\(b\_2>a\_1b\_1,b\_1>a\_2b\_2\\)时  
    无论\\(b\_2,b\_1\\)大小关系如何，都能由\\(a\_1,a\_2\\in \\mathbb\{N+\}\\)推出矛盾。

综上所述，当

\\\[a\_1b\_1>a\_2b\_2\\\]

时，需要交换。

即按照\\(a\_ib\_i\\)升序排列。

### 代码 ###

**需要使用高精**

这句话说着轻松，其实是这题调试的核心。。我习惯重载

#include<algorithm> #include<cstdio> using namespace std; const int MAXN=1005,MAXDIGIT=5005; int n,ak,bk; struct LongInt { short num[MAXDIGIT]; int d; }; struct person { int a; int b; }s[MAXN]; LongInt temp,ans; inline LongInt read() { LongInt temp,ret; temp.d=ret.d=0; char c=getchar(); while(c<'0'||c>'9'); while(c>='0'&&c<='9') { temp.num[++temp.d]=c-'0'; c=getchar(); } for(int i=temp.d;i>=1;i--) ret.num[++ret.d]=temp.num[i]; return ret; } inline void write (LongInt x) { for(int i=x.d;i>=1;i--) putchar(x.num[i]+'0'); } LongInt operator + (LongInt n1,LongInt n2) { LongInt ret; int len=max(n1.d,n2.d)+1; for(int i=1;i<=len;i++) { ret.num[i]=0; if(i<=n1.d) ret.num[i]+=n1.num[i]; if(i<=n2.d) ret.num[i]+=n2.num[i]; ret.num[i+1]+=(ret.num[i]/10); ret.num[i]%=10; } while(!ret.num[len]) len--; ret.d=len; return ret; } LongInt operator * (LongInt n1,LongInt n2) { LongInt ret; int l1=n1.d,l2=n2.d; ret.d=n1.d+n2.d; for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) ret.num[i+j-1]=0; for(int i=1;i<=l1;i++) { for(int j=1;j<=l2;j++) { ret.num[i+j-1]+=n1.num[i]*n2.num[j]; ret.num[i+j]+=ret.num[i+j-1]/10; ret.num[i+j-1]%=10; } } while(!ret.num[ret.d]) ret.d--; return ret; } LongInt operator / (LongInt n1,int n2) { int r=0,len=n1.d; for(int i=len;i>0;i--) { r*=10; r+=n1.num[i]; n1.num[i]=r/n2; r%=n2; } while(!n1.num[n1.d]) n1.d--; return n1; } bool operator < (LongInt n1,LongInt n2) { if(n1.d!=n2.d) return n1.d<n2.d; for(int i=n1.d;i>=1;i--) if(n1.num[i]!=n2.num[i]) return n1.num[i]<n2.num[i]; } LongInt trans (int x) { LongInt ret; ret.d=0; while(x) { ret.num[++ret.d]=x%10; x/=10; } return ret; } int comp(person p1,person p2) { return p1.a*p1.b<p2.a*p2.b; } int main() { scanf("%d",&n); scanf("%d%d",&ak,&bk); for(int i=1;i<=n;i++) scanf("%d%d",&s[i].a,&s[i].b); sort(s+1,s+1+n,comp); temp=trans(ak); for(int i=1;i<=n;i++) { ans=max(ans,temp/s[i].b); temp=temp*trans(s[i].a); } write(ans); return 0; }

转载于:https://www.cnblogs.com/ehznehc/p/11609196.html