[NOIp 2012] 国王的游戏

洛谷 1080

对于队列中的两个人,\(A,B\),其左手上的数字分别是\(a_1,a_2\),右手上的数字分别是\(b_1,b_2\),他们前面的所有人(包括国王)左手上的数字之乘积为 M

则
如果 1 号在前，2 号在后，则应为 \(S_1=max\{ M/b_1,M\times a_1/b_2\}\)
如果 2 号在前，1 号在后，则应为 \(S_2=max\{ M/b_2,M\times a_2/b_1\}\)

很显然应取 \(min\{S_1,S_2\}\)

因为很明显 \(M\times a_2/b_1>M/b_1,M\times a_1/b_2>M/b_2\),那么如果\(S_1,则有 \(M\times a_1/b_2 < M\times a_2/b_1\)

即 \(a_1\times b_1

反推之,发现如果有\(a_1\times b_1,则有\(S_1
即"如果\(a_1\times b_1",则应该让 1 号站在前面

所以按照\(a_i\times b_i\)排个序然后写写高精度就好了

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int width=4,base=10000,MAXN=1e5+1;
char buf[MAXN*width+1];
struct Mint {
	int l,r;
	Mint(int a=0,int b=0):l(a),r(b) {}
	bool operator < (const Mint& rhs) const {
		return l*r=a.len && !g) break;
//		for(int j=0;;j++) {
//			if(j>=b.len && !g) break;
//			c.s[i+j]+=g+a.s[i]*b.s[j];
//			g=c.s[i+j]/base;
//			c.s[i+j]%=base;
//			c.len=max(c.len,i+j+1);
//		}
//	}
//	while(!c.s[c.len-1] && c.len>1) c.len--;
//}
inline void mul(BigInt a,const int &b,BigInt& c) {
	c.clear();
	int g=0;
	for(int i=0;; i++) {
		if(i>=a.len && !g) break;
		c.s[c.len++]=(g+(long long)a.s[i]*b)%base;
		g=(g+(long long)a.s[i]*b)/base;
	}
}
inline void div(BigInt& a,const int &b,BigInt& c) {
	memcpy(c.s,a.s,sizeof(a.s));
	c.len=a.len;
	int g=0;
	for(int i=c.len-1; i>=0; i--) {
		g=g*base+c.s[i];
		c.s[i]=g/b;
		g%=b;
	}
	while(!c.s[c.len-1] && c.len>1) c.len--;
}
inline void scanf(BigInt& n) {
	n.clear();
        scanf("%s",buf);
	for(int i=l-1,j=1,k=1,g=0; i>=0; i--,j++) {
		 g+=(buf[i]-'0')*k;
		if(j%width==0 || i==0) {
			n.s[n.len++]=g;
			g=0;
			k=1;
		} else {
			k*=10;
		}
	}
}
inline void printf(BigInt& n,int endc) {
	if(!n.len) {
		printf("Empty!");
		return;
	}
	printf("%d",n.s[n.len-1]);
	for(int i=n.len-2; i>=0; i--) {
		printf("%04d",n.s[i]);
	}
    	if(endc) putchar(endc);
}
int compare(BigInt& a,BigInt& b) {//ab返回-1
	if(a.len!=b.len) return a.len=0; i--) if(a.s[i] != b.s[i]) return a.s[i]