原題傳送門(mén)：威威貓系列故事——吃雞腿

題目如下（添加了部分陷阱提示，以加粗加下劃線(xiàn)顯示） Problem Description 　　威威貓不是一只普通的貓，普通的貓喜歡吃魚(yú)，但威威貓最喜歡吃雞腿。他每天都在不停的吃啊吃，吃了一只又一只雞腿。現(xiàn)在他遇到了一個(gè)難題，如果他的體重太胖那么他的主人就不給他吃雞腿了，所以他需要你的幫助。
　　威威貓的身體由n個(gè)器官構(gòu)成，由于他的身體很特殊所以他的增長(zhǎng)也很特殊（不要問(wèn)為什么，喜歡吃雞腿的貓已經(jīng)夠奇怪了）。他的增長(zhǎng)有個(gè)k1和k2系數(shù)，而且每天的增長(zhǎng)量和前一天有關(guān)，我們假設(shè)這n個(gè)器官在第i天的數(shù)值分別是a(i,1), a(i,2), a(i,3) …… a(i,n)，那么，第i+1天他每個(gè)器官的數(shù)值就會(huì)變成:
　　a(i+1,1) = k1 * a(i,1) + k2 * a(i,2)
　　a(i+1,2) = k1 * a(i,2) + k2 * a(i,3)
　　......
　　a(i+1,n) = k1 * a(i,n) + k2 * a(i,1)
　　威威貓的體重等于他的所有器官的數(shù)值之和，并且他還擁有一個(gè)特殊的機(jī)能，就是會(huì)自動(dòng)檢測(cè)自己的體重，如果他的體重比K大，那么就會(huì)自動(dòng)停止生長(zhǎng)（為了每天都能吃到雞腿），由于威威貓的特殊身體構(gòu)造他的體重是可能會(huì)變成負(fù)數(shù)的。
　　現(xiàn)在我給你n個(gè)器官的初始數(shù)值和他的增長(zhǎng)系數(shù)k1,k2，請(qǐng)問(wèn)他幾天之后會(huì)停止生長(zhǎng)（如果初始體重已經(jīng)比K大，則是0天后停止生長(zhǎng)），如果他永遠(yuǎn)無(wú)法停止生長(zhǎng)那么就輸出"inf"。(引號(hào)不用輸出) ? Input 輸入數(shù)據(jù)第一行是一個(gè)正整數(shù)T，表示有T組測(cè)試數(shù)據(jù)；
每組數(shù)據(jù)的第一行包含4個(gè)數(shù)字n,k1,k2,k，代表威威貓有n個(gè)器官，他的生長(zhǎng)系數(shù)是k1、k2（可能是小數(shù)），當(dāng)體重超過(guò)k的時(shí)候他就停止生長(zhǎng)。
接下來(lái)的一行是n個(gè)數(shù)ai，代表威威貓每個(gè)器官第一天的數(shù)值是多少。

[Technical Specification]
T <= 100
1 <= n <= 10000
-100 <= k1, k2 <= 100
1 <= k <= 10 ^ 18
1 <= ai <= 1000（1 <= i <= n）? ?

?

Output 對(duì)于每組測(cè)試數(shù)據(jù)，請(qǐng)首先輸出"Case #X: "，X代表測(cè)試用例的編號(hào)，然后輸出一個(gè)數(shù)ans，代表ans天之后他會(huì)停止生長(zhǎng)，如果不會(huì)停止就輸出inf
具體可參見(jiàn)sample output。 ?

?

Sample Input 2 5 1 1 10 1 1 1 1 1 5 1 1 500 1 1 1 1 1 ?

?

Sample Output Case #1: 2 Case #2: 7 題目分析： 將題目給出的所有遞推公式相加（左端相加，右端相加），整理后得到一個(gè)體重增長(zhǎng)的遞推公式：W_i+1?= (k₁ + k₂)W_i,由此可見(jiàn)如果初始體重不大于k的話(huà)，那么（k₁+k₂）就是導(dǎo)致體重增大或縮小的因素。當(dāng)|k₁+k₂| <= 1時(shí)，體重將永遠(yuǎn)不會(huì)超過(guò)給定的k值。因此代碼如下：
1 package org.contests; 2 3 import java.util.Scanner; 4 5 public class ChickenLegs { 6 public static void main(String[] args) { 7 Scanner scan = new Scanner(System.in); 8 int totalGroupNum = scan.nextInt(); 9 for(int ti = 0; ti < totalGroupNum; ti++){ 10 int rowNum = scan.nextInt(); 11 double k1 = scan.nextDouble(); 12 double k2 = scan.nextDouble(); 13 long k = scan.nextLong(); 14 int dayNum = 1; 15 boolean isInf = false; 16 17 double totalWeight = 0; 18 19 for(int ri = 0; ri < rowNum; ri++){ 20 totalWeight += scan.nextInt(); 21 } 22 23 while(totalWeight <= k){ 24 25 if(Math.abs(k1 + k2) <= 1){// | k1 + k2 | <= 1 26 isInf = true; 27 break; 28 } 29 30 totalWeight = (k1 + k2) * totalWeight; 31 dayNum++; 32 } 33 34 if(isInf){ 35 System.out.println("Case #"+(ti+1)+": inf"); 36 }else{ 37 System.out.println("Case #"+(ti+1)+": "+(dayNum-1)); 38 } 39 } 40 } 41 }

?

?

在HDU提交時(shí)，java代碼不需要package語(yǔ)句，需要把public類(lèi)的類(lèi)名改為Main，下列代碼是在HDU提交AC了的代碼：

1 import java.util.Scanner; 2 3 public class Main{ 4 public static void main(String[] args) { 5 Scanner scan = new Scanner(System.in); 6 int totalGroupNum = scan.nextInt(); 7 for(int ti = 0; ti < totalGroupNum; ti++){ 8 int rowNum = scan.nextInt(); 9 double k1 = scan.nextDouble(); 10 double k2 = scan.nextDouble(); 11 long k = scan.nextLong(); 12 int dayNum = 1; 13 boolean isInf = false; 14 15 double totalWeight = 0; 16 17 for(int ri = 0; ri < rowNum; ri++){ 18 totalWeight += scan.nextInt(); 19 } 20 21 while(totalWeight <= k){ 22 23 if(Math.abs(k1 + k2) <= 1){// | k1 + k2 | <= 1 24 isInf = true; 25 break; 26 } 27 28 totalWeight = (k1 + k2) * totalWeight; 29 dayNum++; 30 } 31 32 if(isInf){ 33 System.out.println("Case #"+(ti+1)+": inf"); 34 }else{ 35 System.out.println("Case #"+(ti+1)+": "+(dayNum-1)); 36 } 37 } 38 } 39 }

吐槽：

由于學(xué)藝不精加之題目有些陷阱，此題在規(guī)定時(shí)間內(nèi)我么有完成，還差得很遠(yuǎn)額~~

轉(zhuǎn)載于:https://www.cnblogs.com/FlameRen/archive/2013/03/26/2981996.html

總結(jié)

以上是生活随笔為你收集整理的【腾讯第二届校园编程马拉松】HDU-4525，威威猫系列故事——吃鸡腿的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。