- 国王游戏
- 2014-10-12 21:38:55 @
我的贪心标准是对于两个人A和B,取"A在左,B在右"和"B在左,A在右"两种情况下的右边的人获得的钱较少的那种情况。
但是如果直接相除再比较两种情况下的结果大小只能拿20分,把除法式子移项变成乘法之后就能AC。为什么?题目里既然说了向下取整的话,不是应该用除法做才更正确吗?
6 条评论
-
westfallon LV 8 @ 2017-05-28 11:01:10
求大神拯救!为啥才过两个点
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,l,r,a[1001],b[1001],e,f,en;
int j(int m);
int c(int m);
int main()
{
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
int max=0,y,min;
for(int i=1;i<=n;i++)
{
if(j(i)>=max)
{
max=j(i);
y=i;
}
}
e=a[y];
f=b[y];
for(int i=y;i<n;i++)
{
a[i]=a[i+1];
b[i]=b[i+1];
}
n--;
min=l/f;en=0;
for(int i=1;i<=n;i++)
{
int p;
p=c(i)/f;
if(p<=min)
{
min=p;
en=i;
}
}
for(int i=n+1;i>en+1;i--)
{
a[i]=a[i-1];
b[i]=b[i-1];
}
a[en+1]=e;b[en+1]=f;n++;
max=0;
for(int i=1;i<=n;i++)
{
if(j(i)>max)
max=j(i);
}
cout<<max<<endl;
return 0;
}
int j(int m)
{
int x=l;
for(int i=1;i<m;i++)
x=x*a[i];
x=x/b[m];
return x;
}
int c(int m)
{
int x=l;
for(int i=1;i<=m;i++)
x=x*a[i];
return x;
} -
2016-09-17 16:36:40@
我来挖个坟。。。因为换做乘法才能AC有两个理由1.不会得到比直接相除更差的节(易证)2.假如使用取整,虽然在这一位置两者相当,但是可能会导致后面的人获得的金币数增加
-
2015-03-05 12:34:35@
请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这n位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
格式
输入格式第一行包含一个整数n,表示大臣的人数。
第二行包含两个整数a和b,之间用一个空格隔开,分别表示国王左手和右手上的整数。接下来n行,每行包含两个整数a和b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
输出格式输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
样例1
样例输入1[复制]3
1 1
2 3
7 4
4 6
样例输出1[复制]2
限制
每个测试点1s
提示
对于20%的数据,有1≤ n≤ 10,0 < a、b < 8;
对于40%的数据,有1≤ n≤20,0 < a、b < 8;
对于60%的数据,有1≤ n≤100;
对于60%的数据,保证答案不超过10^9;
对于100%的数据,有1 ≤ n ≤1,000,0 < a、b < 10000。
来源
Noip2012提高组复赛Day1T2
递交评测
查看题解
查看本题递交记录
我的记录
我的所有递交记录
您没有递交记录
题目讨论
发表题目讨论
12-17 关于贪心的标准
UPYUN
评测机们Jtwd2
树形图设计者
上海红茶馆
VijosEx
Vijos 2.0 动态2014-9-16 网络维护
2014-9-25 备案完毕
2014-9-28 更换服务器
2014-11-28 微小更新
实验室 | API | 博客 | 帮助 | 隐私 | 联系 | 关于 | 沪ICP备14040537号
© Copyright Vijos, 137a2bc beta, in 46.78988 ms -
2014-10-13 21:27:36@
看标题的时候我错认为是一个哲学问题。。。
-
2014-10-13 18:14:54@
Orz
-
2014-10-12 22:14:41@
我记得我是瞎贪的
- 1