本文共 1378 字,大约阅读时间需要 4 分钟。
标签: 思维&逻辑
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):最后,情况12可以合并一下,第1种情况下,X==Y,所以有Z<=11*K*X/(11*Y+2*X),与情况2相同.
#includeint 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;}
转载地址:http://askxi.baihongyu.com/