[NOIP2012 提高组] 国王游戏（贪心，排序，高精度）

[NOIP2012 提高组] 国王游戏

题目描述

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 $n$，表示大臣的人数。

第二行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例 #1

样例输入 #1

3 
1 1 
2 3 
7 4 
4 6
1
2
3
4
5

样例输出 #1

2
1

提示

【输入输出样例说明】

按 $1$、$2$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $1$、$3$、$2$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $2$、$1$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 2$、$3$、$1 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$；

按 $3$、$1$、$2 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 3$、$2$、$1$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$。

因此，奖赏最多的大臣最少获得 $2$ 个金币，答案输出 $2$。

【数据范围】

对于 $20\%$ 的数据，有 $1\le n\le 10,0<a,b<8$；

对于 $40\%$ 的数据，有$ 1≤ n≤20,0 < a,b < 8$；

对于 $60\%$ 的数据，有 $1\le n\le 100$；

对于 $60\%$ 的数据，保证答案不超过 $10^9$；

对于 $100\%$ 的数据，有 $1\le n\le 1,000,0<a,b<10000$。

NOIP 2012 提高组 第一天 第二题

瞎贪心环节

• 由于在队列最末端时，当前大臣前所有的大臣左手数的乘积一定是最大的，那么最后面的大臣右手的数要最小才能满足需求
• 因此，我们可以得出一个正确性未定的贪心结论：将大臣右手数进行从小到大排序，这就是最优排序。

证明嘛我不会，贪心本身不就是半玄学

咳咳，总之，我们根据以上结论可以得出以下代码

#include
#include
#include
#include
#include
using namespace std;
const int N=1e3+231;
int n,kl,kr;
long long int ans=0;
struct node{
	int le,ri;
}a[N];
bool cmp(node aa,node bb){
	return aa.ri<bb.ri;
}
int main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	cin>>n;
	cin>>kl>>kr;
	for(int i=1;i<=n;i++){
		cin>>a[i].le>>a[i].ri;
	}
	sort(a+1,a+1+n,cmp);
	int mul=kl;
	for(int i=1;i<=n;i++){
	//	ans=max(ans,mul/a[i].ri);
		if(ans<(mul/a[i].ri))ans=mul/a[i].ri;
		mul*=a[i].le;
		//cout<
	}
	cout<<ans<<endl;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

非~~常简短，但是，这只能拿到50分。

由于a，b的大小过大，long long int会爆，我们需要高精度。（此贪心思路下高精度只能得到90分，若想真正AC，那需要另一个贪心思路）

如果第 i 个大臣放第 j 个大臣前面对答案的贡献小些,那么第 i 个大臣就放第 j 个大臣前面所以就是使 $$a[i].x/a[j].y<a[j].x/a[i].y$$
所以就是$$a[i].x\ast a[i].y<a[j].x\ast a[j].y$$

#include
#include
#include
using namespace std;
struct node{
	int a,b;
	char cnta[10000],all[10000];//cnta 为前面所有a的乘积的逆序 all为乘积正序 
	char ca[100];//a转化为字符数组 
	char ans[10000];//所获得金币数 
	int lans;
}da[1001];
bool cmp(node a,node b){
	return a.a*a.b<b.a*b.b;
}
bool cmp2(node a,node b){//高精度比较 
	if(a.lans!=b.lans)
		return a.lans>b.lans;
	else{
		int i;
		for(i=0;i<a.lans;i++)
			if(a.ans[i]==b.ans[i]) {
				continue;
			}
			else return a.ans[i]>b.ans[i];
	}
	return 1==1;
}
void doit(int a,char b[]){//将数值转化成字符数组
	int lb=0;
	while(a>0){
		b[lb++]=a%10+'0';
		a/=10;
	}
	b[lb]='\0';
}
void add(char c[],char d[],int i){//错位相加 
	int lc=strlen(c),j;
	int jw = 0,tmp;
	for(j=0;j<lc;j++,i++){
		tmp=(d[i]>0?d[i]-'0':0)+c[j]-'0'+jw;
		d[i]=tmp%10+'0';
		jw=tmp/10;
	}
	if(jw){
		d[i++]=jw+'0';
	}
	d[i]='\0';
}
void gc(char a[],char b[],char d[]){//高乘 
	int la=strlen(a);
	int lb=strlen(b);
	int i,j;
	char c[10000];
	for(i=0;i<la;i++){
		int tmp;
		int jw = 0;
		int lc = 0;
		for(j=0;j<lb;j++){
			tmp = (a[i]-'0') * (b[j]-'0') + jw;
			c[lc++] = tmp % 10 + '0';
			jw = tmp / 10;
		}
		if(jw) c[lc++]=jw+'0';
		c[lc]='\0';
		add(c,d,i);
	}
}
void mult(char a[],int b, char c[]){
	int i = 0 , tag = 0 , la = strlen(a) , lc = 0;
	int d = 0;
	while(i<=la){
		if(b>d){
			d=d*10+a[i++]-'0';
			if(tag) c[lc++]='0';
		}else{
			c[lc++]=d/b+'0';
			d=d%b;
			d=d*10+a[i++]-'0';
			tag = 1;
		}
	}
	if(tag==0)c[lc++]='0';
	c[lc]='\0';
}
int main(){
	int n,i,j;
	memset(da,0,sizeof(da));
	scanf("%d",&n);
	scanf("%d%d",&da[0].a,&da[0].b);
	for(i=1;i<=n;i++){
		scanf("%d%d",&da[i].a,&da[i].b);
	}
	sort(da+1,da+n+1,cmp);
	doit(da[0].a,da[0].ca); 
	da[0].cnta[0]='1';
	da[0].cnta[1]='\0';
	for(i=1;i<=n;i++){
		doit(da[i].a,da[i].ca);
		gc(da[i-1].cnta,da[i-1].ca,da[i].cnta);
	}
	for(i=1;i<=n;i++){//将乘积逆转 
		int k=0;
		for(j=strlen(da[i].cnta)-1;j>=0;j--)
			da[i].all[k++]=da[i].cnta[j];
		da[i].all[k]='\0';
	}
	for(i=1;i<=n;i++){
		mult(da[i].all,da[i].b,da[i].ans);
		da[i].lans = strlen(da[i].ans);
	}
	int ans = 1;
	for(i=2;i<=n;i++){
		if(!cmp2(da[ans],da[i]))
			ans=i;
	}
	printf("%s\n",da[ans].ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

封面