洛谷【P1080】国王游戏

我对贪心的理解：https://www.cnblogs.com/AKMer/p/9776293.html

题目传送门：https://www.luogu.org/problemnew/show/P1080

对于很多要求一个序列使得结果最优，那么这个序列该怎么排的题目，我们都可以用微扰的思想来解决。

假定我们已经求出了最优序列，并且在这个顺序下，交换任意两项都不会更优。因为交换任意两项可以通过交换相邻两项得来，所以也就是交换任意相邻两项不会更优。

令\(fake[i]\)等于\(\prod\limits_{j=0}^{j=i}left[i]\)。对于任意\(i,i+1\)存在：

交换前，他们分别拿到：

\(fake[i-1]/right[i]\)，\(fake[i-1]*left[i]/right[i+1]\)

交换后分别得到：

\(fake[i-1]/right[i+1]\)，\(fake[i-1]*left[i+1]/right[i]\)

由于任意交换都不会使得结果更优，所以：

\(max(fake[i-1]/right[i],fake[i-1]*left[i]/right[i+1])<=max(fake[i-1]/right[i+1],fake[i-1]*left[i+1]/right[i])\)

提出公因式：

\(max(1/right[i],left[i]/right[i+1])<=max(1/right[i+1],left[i+1]/right[i])\)

则\(1/right[i+1]\)与\(left[i+1]/right[i]\)这两个数中，必然有一个数同时大于等于\(1/right[i]和left[i]/right[i]\)。因为\(1/right[i+1]<=left[i]/right[i+1]\)，所以\(left[i+1]/right[i]>=left[i]/right[i+1]\)。

所以对于任意\(i\)，\(i+1\)，都存在：

\(left[i]*right[i]<=left[i+1]*right[i+1]\)

按这个排序然后模拟就行了。

时间复杂度：\(O(n*高精度)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=1005,pps=10000;

int n;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct person {

	int lft,rgt;

	bool operator<(const person &a)const {

		return lft*rgt<a.lft*a.rgt;

	}

}p[maxn];

struct Bignum {

	int num[1050];

	void clear() {

		memset(num,0,sizeof(num));

	}

	void init() {

		clear();num[0]=num[1]=1;

	}

	Bignum operator*(const int &a)const {

		Bignum c;c.clear();c.num[0]=num[0];

		for(int i=1;i<=num[0];i++) {

			c.num[i]+=num[i]*a;

			c.num[i+1]+=c.num[i]/pps;

			c.num[i]%=pps;

		}

		if(c.num[c.num[0]+1])c.num[0]++;

		return c;

	}

	Bignum operator/(const int &a)const {

		Bignum c;c.clear();c.num[0]=num[0];

		int tmp=0;

		for(int i=num[0];i;i--) {

			c.num[i]=(tmp*pps+num[i])/a;

			tmp=(tmp*pps+num[i])%a;

		}

		while(!c.num[c.num[0]]&&num[0])c.num[0]--;

		return c;

	}

	bool  operator<(const Bignum &a)const {

		if(num[0]!=a.num[0])return num[0]<a.num[0];

		for(int i=num[0];i;i--)

			if(a.num[i]!=num[i])

				return num[i]<a.num[i];

		return 1;

	}

	void print() {

		printf("%d",num[num[0]]);

		for(int i=num[0]-1;i>0;i--)

			printf("%04d",num[i]);

	}

};

int main() {

	n=read();

	for(int i=0;i<=n;i++)

		p[i].lft=read(),p[i].rgt=read();

	sort(p+1,p+n+1);Bignum tmp,ans;

	ans.clear();tmp.init();tmp=tmp*p[0].lft;

	for(int i=1;i<=n;i++) {

		ans=max(ans,tmp/p[i].rgt);

		tmp=tmp*p[i].lft;

	}ans.print();

	return 0;

}

巴特西

洛谷【P1080】国王游戏

最新文章

热门文章