hdu6245 Rich Game - CSDN博客

原题链接:Rich Game(hdoj/hdu6245) ?
文章价值(3) ?
阅读数(413) ?

hdu6245 Rich Game

标签: 思维&逻辑


题目链接

题意:

Sheep找Panda打羽毛球。Sheep说,我每赢一分我给你X元,但我每输一分你要给我Y元(题目问的是Panda最多能够赢多少场比赛,转化一下,对Panda来说,他每赢一分给对手Y元,输一分获得X元)。比赛K场。

一场比赛赢的情况:
(1)某人至少得11分,且至少领先对手2分(即11:9)。
(2)通常某人先得10分他就会赢得比赛,若出现平手(例如10:10),则他应该至少领先对手2分才能赢得这场比赛,个人得分可能会超过11分。

Panda能力超强,可以控制每一分的输赢。但他开始时没有钱,他必须通过输分来获得钱,然后用这些钱去赢得比赛。
Panda不能够欠Sheep钱。
问Panda最多能够赢多少场比赛?
T组测试样例,每组为X Y K。

分析:

前提条件:Panda不能够欠Sheep钱,所以比赛中所有的钱会>=0。
一共K局比赛,假设Panda赢了Z局,则Panda输了(K-Z)局。所以,有

11*(K-Z)*X + a*Z*X-(a+2)*Z*Y >= 0,记为(1)式。

解释一下上面这个式子:
前半部分,11*(K-Z)*X,这部分是Panda输的局,所以Panda要输的干干脆脆的,一分也不赢,这样Panda才能得到最多的钱;
后半部分,假设panda某局得分为(a+2),因为Panda应该至少领先对手2分才能赢得这场比赛。

化简(1)式,把Z提出来,得

Z*(11*X+2*Y+a*(Y-X))<=11*K*X,记为(2)式。

题目求的是,Panda最多能够赢得多少场比赛。看下方程,右边是一个常数,所以要使得Z尽可能大,(11*X+2*Y+a*(Y-X))要尽可能小,即a*(Y-X)要尽可能小。
下面分情况讨论a*(Y-X):

  1. X==Y,方程与a无关,Z<=11*K*X/(11*X+2*Y).
  2. X < Y,即(Y-X) > 0,因为要使得a*(Y-X)尽可能小,所以a要尽可能小,而a>=9(一场比赛赢的情况之(1):某人至少得11分,且至少领先对手2分,即9:11的情况),把a代入方程得,Z<=11*K*X/(11*Y+2*X).
  3. X > Y,即(Y-X) < 0,因为要使得a*(Y-X)尽可能小,所以a要尽可能大,a可以很大很大。回到(2)式,a很大,(Y-X)<0,a*(Y-X)很小,(11*X+2*Y+a*(Y-X))很小,则Z很大,Z最大为K,即每场比赛都是Panda赢。(通俗的说,也就是Panda输一分得到的钱比赢一分得到的钱都要多,想想就明白了。)

最后,情况12可以合并一下,第1种情况下,X==Y,所以有Z<=11*K*X/(11*Y+2*X),与情况2相同.

代码:

#include 

int main(){
    int t, x, y, k, kase = 0;

    scanf("%d", &t);
    while(t--){
        scanf("%d %d %d", &x, &y, &k);
        printf("Case #%d: %d\n", ++kase, x > y ? k : 11 * k * x / (11 * y + 2 * x);
    }
    return 0;
}




(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: