題目鏈接：點擊查看

題目大意：恰逢 H 國國慶,國王邀請 n 位大臣來玩一個有獎游戲。首先,他讓每個大臣在左、右手上面分別寫下一個整數,國王自己也在左、右手上各寫一個整數。然后,讓這 n 位大臣排成一排,國王站在隊伍的最前面。排好隊后,所有的大臣都會獲得國王獎賞的若干金幣,每位大臣獲得的金幣數分別是:排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數,然后向下取整得到的結果。
國王不希望某一個大臣獲得特別多的獎賞,所以他想請你幫他重新安排一下隊伍的順序,使得獲得獎賞最多的大臣,所獲獎賞盡可能的少。注意,國王的位置始終在隊伍的最前面。

題目分析：

先說結論，按照每個大臣的a*b大小升序排序就能得到最優解

證明如下：

首先我們交換第i個位置和第i+1個位置的兩個大臣，在此之前他們兩人的獎勵分別是：

和

交換之后變為

和

為了方便觀察，我們約分約去

則我們只需要比較下面兩個式子的大小關系：

和

兩邊同時乘上得：

和

因為A[i]和B[i]都為正整數，所以且

于是當時，左式<=右式，交換前更優，否則交換后更優，所以在任何局面下，減小逆序對數都不會造成整體結果變差，而增加逆序對數則不會使整體結果變好，證畢

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=40100;//最大長度const string ss="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";int mp[150]; void postpoint(string& a)//移位處理 {int len=a.size();a.resize(N);for(int i=0;i<len;i++){a[N-i-1]=a[len-i-1];a[len-i-1]=0;} }string change(const string& a)//用于解除postpoint {string ans;for(int i=0;i<N;i++)if(a[i])ans+=a[i];return ans; }string plu(string a,string b,int base=10) {postpoint(a);postpoint(b);string temp;temp.resize(N);int f=0;for(int i=N-1;a[i]||b[i]||f;i--){a[i]==0?a[i]='0':0;b[i]==0?b[i]='0':0;temp[i]=(mp[a[i]]+mp[b[i]]+f)%base;f=(mp[a[i]]+mp[b[i]]+f)/base;temp[i]=ss[temp[i]];}return change(temp); }string mul(string a,int n,int base=10) {postpoint(a);string temp;temp.resize(N);int f=0;for(int i=N-1;a[i]||f;i--){a[i]==0?a[i]='0':0;temp[i]=(mp[a[i]]*n+f)%base;f=(mp[a[i]]*n+f)/base;temp[i]=ss[temp[i]];}return change(temp); }string Except(string s,long long x) //大數除以整形數 {long long cmp=0;bool ok=false;string ans="";for(int i=0;i<s.size();i++){cmp=(cmp*10+s[i]-'0');if(cmp>=x){ok=true;ans+=(cmp/x+'0');cmp%=x;}else{if(ok)ans+='0'; //注意這里}}return ans; }void init() {for(int i=0;i<ss.size();i++)mp[ss[i]]=i; }struct Node {int a,b;bool operator<(const Node& t)const{return a*b<t.a*t.b;} }a[10100];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n;scanf("%d",&n);for(int i=0;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b);sort(a+1,a+1+n);string ans=to_string(a[0].a);string mmax;for(int i=1;i<=n;i++){string temp=Except(ans,a[i].b);if(temp.size()>mmax.size()||temp>mmax)mmax=temp;ans=mul(ans,a[i].a);}cout<<mmax<<endl; return 0; }

?

總結

以上是生活随笔為你收集整理的CH - 0701 国王游戏(贪心+高精度运算)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。