洛谷p1080 国王游戏 （搞清不等式关系）

题目描述

国王想玩一个游戏，让所有的大臣排成一个队伍，每人左右手上各写一个整数（包括国王），每位大臣的获赏金币为：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。 注意，国王的位置始终在队伍的最前面。 输出：重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

题目分析

大臣的排列有n！种，国王要找到一种或多种排列，使得该种排列种获得金币数目最多的大臣是所有排列种获得金币数目最少的！ 分析可以得出，对相邻的两个大臣如果交换位置，则对前面的大臣、后面的大臣都没有任何影响，所以我们考量相邻的两个大臣是否要交换。（没看懂洛谷的题解，自己又重新写了遍~~） 所以排序方式即为 根据大臣左右的数值乘积进行排序，乘积小的要在前面，才能出现此排列中的最大金币数为所以排列中的最小值。 注意：要用到高精度运算

AC代码

/* Author:snnu_lgw Date：2020/7/2 */ #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; struct Node{ string a; ll b; }node[1000+10]; string f[1000+10];//记录每一个大臣获得的金币数目 int ans[50001];//高精度乘法所用 string multi(string str1,string str2) { //高精度的乘法 string str; int len1 = str1.length(), len2 = str2.length(); int len = len1+len2-1; int ca_bit = 0;//进位 for(int i=0;i<=len1+len2;i++) ans[i] = 0;//清空前面的数据 for(int i=len1-1;i>=0;i--) for(int j=len2-1;j>=0;j--)//记录按位乘的数据 ans[i+j] += (str1[i]-'0')*(str2[j]-'0'); for(int i=len-1;i>=0;i--) {//转换为字符串存储 int temp = ans[i]+ca_bit; ca_bit = temp/10;//进位 temp%=10;//本位 str = char(temp+'0')+str; } if(ca_bit>0) str = char(ca_bit+'0')+str; if(str[0]=='0') str = "0"; //依据上述计算过程，可能会出现前导0，而且可能不止一个，如果有前导0，那么结果必为0 return str; } string div(string a,ll b) { // 高精度除以低精度求值 string str; ll num = 0;//被除数 ll flag = 0; //判断a是否大于b for(int i=0;i<a.length();i++) { num = num*10+(a[i]-'0'); ll quo = num/b;//商 if(quo != 0) flag++; if(flag==0) continue;//除法开始时被除数是不够大的，但是一旦被除数够大了，就不能再continue了，而是上0. num = num%b;//更新被除数的值 str = str+char(quo+'0'); } if(flag == 0)//表明a小于b str = "0"; return str; } string ll_to_string(ll a) {//将一个整型数据转化为字符串存储 string str; while(a) { int k = a%10; str = char(k+'0')+str; a/=10; } return str; } bool cmp(Node n1,Node n2) {//排序的方法 string str1 = multi(n1.a,ll_to_string(n1.b)); string str2 = multi(n2.a,ll_to_string(n2.b)); return (((str1<str2)&&(str1.length()==str2.length()))||(str1.length()<str2.length())); } int main() { cin>>n; int kb; string ka; cin>>ka>>kb; for(int i=1;i<=n;i++) cin>>node[i].a>>node[i].b; /* for(int i=1;i<=n;i++) {//输出检验，单步调试 string str = multi(node[i].a,ll_to_string(node[i].b)); cout<<node[i].a<<" "<<ll_to_string(node[i].b)<<" "<<str<<endl; } */ sort(node+1,node+n+1,cmp); string fmax;//金币的最大值 string str = ka; //国王的左手数据 for(int i=1;i<=n;i++) { f[i] = div(str,node[i].b); //金币数 str = multi(str,node[i].a);//累乘 if((fmax<f[i]&&fmax.length()==f[i].length())||fmax.length()<f[i].length()) fmax = f[i]; } cout<<fmax;//输出最大值 return 0; }

参考资料：洛谷题解