Description
牛客网 校招真题 整数成绩最大化
Solving Ideas
当n>4时，最大受益为尽可能拆分出更多的数字3，最后一个不足3的，若其为1则分给其中一个3，得到4，若其为2则乘上去。
为什么不是最大收益不是4以上呢？
例如5，5可分解为2*3，收益能通过继续分解得到增加。
Time complexity : O ( l o g n ) O(logn) O(logn)
Space complexity : O ( 1 ) O(1) O(1)
Solution
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*** @author wylu*/public class Main {static int[] products = {0, 0, 1, 2, 4};public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int res;if (n > 4) {int p = n / 3, q = n % 3;if (q == 0) res = (int) Math.pow(3, p);else if (q == 1) res = (int) (Math.pow(3, p - 1) * 4);else res = (int) (Math.pow(3, p) * 2);} else {res = products[n];}System.out.println(res);}}
如果觉得《牛客网 校招真题 招商银行信用卡 整数成绩最大化》对你有帮助，请点赞、收藏，并留下你的观点哦！
