首页 > ACM题库 > HDU-杭电 > hdu 2149 Public Sale-博弈论-[解题报告]C++
2013
12-30

hdu 2149 Public Sale-博弈论-[解题报告]C++

Public Sale

问题描述 :

虽然不想,但是现实总归是现实,Lele始终没有逃过退学的命运,因为他没有拿到奖学金。现在等待他的,就是像FarmJohn一样的农田生涯。

要种田得有田才行,Lele听说街上正在举行一场别开生面的拍卖会,拍卖的物品正好就是一块20亩的田地。于是,Lele带上他的全部积蓄,冲往拍卖会。

后来发现,整个拍卖会只有Lele和他的死对头Yueyue。

通过打听,Lele知道这场拍卖的规则是这样的:刚开始底价为0,两个人轮流开始加价,不过每次加价的幅度要在1~N之间,当价格大于或等于田地的成本价 M 时,主办方就把这块田地卖给这次叫价的人。

Lele和Yueyue虽然考试不行,但是对拍卖却十分精通,而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于Lele字典序比Yueyue靠前,所以每次都是由Lele先开始加价,请问,第一次加价的时候,
Lele要出多少才能保证自己买得到这块地呢?

输入:

本题目包含多组测试,请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述,0<N,M<1100)

输出:

本题目包含多组测试,请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述,0<N,M<1100)

样例输入:

4 2
3 2
3 5

样例输出:

1
none
3 4 5

/*
巴什博弈
先判断是不是先手必败
*/

#include<stdio.h>

int main()
{
    int m, n, i;
    while(scanf("%d%d", &m, &n) != EOF)
    {
        if(m > n) //这种情况先手非必败的话只有一种出法
        {
            if(m % (n + 1) == 0)
            {
                puts("none");
                continue;
            }
            else
                printf("%d\n", m %(n + 1));
        }
        if(m <= n) //这种情况只需输出大于等于m的就行
        {
            for(i = m; i < n; i ++)
                printf("%d ", i);
            printf("%d\n", n);
        }
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/Yu2012/archive/2012/10/20/2731979.html


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”