关于贪心的标准

我的贪心标准是对于两个人A和B,取"A在左,B在右"和"B在左,A在右"两种情况下的右边的人获得的钱较少的那种情况。
但是如果直接相除再比较两种情况下的结果大小只能拿20分,把除法式子移项变成乘法之后就能AC。为什么?题目里既然说了向下取整的话,不是应该用除法做才更正确吗?

6 条评论

  • @ 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 23:53:04

      orz队长

    • @ 2014-10-14 10:27:41

      。。。没那么高的境界= = 只是讨论这道题的贪心标准

  • @ 2014-10-13 18:14:54

    Orz

  • @ 2014-10-12 22:14:41

    我记得我是瞎贪的

    • @ 2014-10-13 12:26:11

      貌似有人说过"最优解可能有很多所以错误的贪心也能AC"。。。比如对于样例,我的上述两种方法虽然序列不同但是得到的最大奖赏相同。。。

  • 1

信息

ID
1779
难度
7
分类
贪心 | 高精度 点击显示
标签
递交数
5344
已通过
959
通过率
18%
被复制
10
上传者