洛谷 P1080 [NOIP2012 提高组] 国王游戏

Descrption

洛谷传送门

Solution

一道非常好的贪心题。

我们只考虑国王以及两个大臣，编号依次为 1，2，3

左手分别写着 (a_1)，(a_2)，(a_3)，右手上分别写着 (b_1)，(b_2)，(b_3)。

对于 2 在前还是 3 在前分别考虑：

• 1 - 2 - 3：

这种情况下： $$ans_1 = max(frac{a_1}{b_2}, frac{a_1 * a_2}{b_3})$$

• 1 - 3 - 2:

此时：$$ans_2 = max(frac{a_1}{b_3}, frac{a_1 * a_3}{b2})$$

代换一下可得：

[ans_1 = max(k_1, k_2) ]

[ans_2 = max(k_3, k_4) ]

容易发现，(k_2 geq k_3) 且 (k_4 geq k_1)

若 (ans_1 < ans_2)，那么 (k_2 < k_4)

即：$$frac{a_1 * a_2}{b_3} < frac{a_1 * a_3}{b_2}$$

两边同乘 (b_2 * b_3)，然后同时除以 (a_1) 可得：$$a_2 * b_2 < a_3 * b_3$$

然后就很简单了，直接对于输入的大臣，按照 (a_i * b_i) 排序即可。

注意要用高精度（这个才是难点）。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1010

using namespace std;


inline int read(){
	int x = 0;
	char ch = getchar();
	while (ch < '0' && ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
}

struct node{
	int num[100000];
	node(){
		memset(num, 0, sizeof(num));
	}
	bool operator > (const node &b) const{
		if(num[0] > b.num[0]) return 1;
		if(num[0] < b.num[0]) return 0;
		for(int i = num[0]; i >= 1; i--){
			if(num[i] > b.num[i]) return 1;
			if(num[i] < b.num[i]) return 0;
		}
		return 0;
	}
	node operator + (const node &b) const{
		node c;
		c.num[0] = min(100, max(num[0], b.num[0]));
		for(int i = 1; i <= c.num[0]; i++)
			c.num[i] = num[i] + b.num[i];
		for(int i = 1; i <= c.num[0]; i++){
			c.num[i + 1] += c.num[i] / 10;
			c.num[i] %= 10;
		}
		if(c.num[c.num[0] + 1]) c.num[0]++;
		return c;
	}
	node operator * (int b) const{
		node c;
		int w = 0;
		c.num[0] = num[0];
		for(int i = 1; i <= c.num[0]; i++){
			c.num[i] = num[i] * b + w;
			w = c.num[i] / 10;
			c.num[i] %= 10;
		}
		if(w) c.num[++c.num[0]] = w;
		while(c.num[c.num[0]] >= 10){
			c.num[c.num[0] + 1] = c.num[c.num[0]] / 10;
			c.num[c.num[0]++] %= 10;
		}
		return c;
	}
	node operator / (const int b) const{
		node c;
		int w = 0;
		for(int i = num[0]; i >= 1; i--){
			w = w * 10 + num[i];
			c.num[i] = w / b;
			w %= b;
		}
		c.num[0] = num[0];
		while(!c.num[c.num[0]] && c.num[0] > 1) c.num[0]--;
		return c;
	}
}ans, tmp, maxs, A;
int B;
struct people{
	int a,b,val;
	bool operator < (const people &b){
		return val < b.val;
	}
}p[N];
int n;

int main(){
	ios :: sync_with_stdio(false);
	cin >> n >> p[1].a >> p[1].b;
	p[1].val = p[1].a * p[1].b;
	for(int i = 2; i <= n + 1; i++){
		cin >> p[i].a >> p[i].b;
		p[i].val = p[i].a * p[i].b;
	}
	sort(p + 2, p + 2 + n);
	ans.num[0] = ans.num[1] = 1;
	for(int i = 2; i <= n + 1; i++){
		ans = ans * p[i - 1].a;
		tmp = ans / p[i].b;
		if(tmp > maxs)
			memcpy(maxs.num, tmp.num, sizeof(tmp.num));
	}
	for(int i = maxs.num[0]; i >= 1; i--)
		cout << maxs.num[i];
	cout << endl;
	return 0;
}

End