兔子打算切出个长方形的小蛋糕来吃,但为了减肥它只打算切一刀,这一刀可能包含n步,每一步可以往横向或纵向走一个单位长度,总长度为n。
假设兔子切的起点是(x,0),问能切出的最大蛋糕面积是多少?需要注意的是,要求蛋糕必须是长方形的。
示例1,在x=1、n=3时,可以切出面积为2的最大蛋糕,刀的走向是:上上左,将角落上的蛋糕切下来。
|←
| ↑
|_↑_ _
示例2,在x=3、n=3时,可以切出面积为1的最大蛋糕,刀的走向是:上右下,将边上的蛋糕切下来。
|
| →
|_ _ _↑_↓_
第一行一个正整数T,表示T个测试样例;
对于每个测试样例,
输入整数x(1=<x<1e4),表示起点(x,0);
接着输入整数n(3=<n<1e4),表示切的长度n。
输出T行,每行一个正整数,表示每个样例能切出的最大面积
2 1 3 100 3
2 1
我的题解A
- 没有AC,但是错误的思路值得记录一下。
读完题目,有一些需要注意的东西
当时解题思路
就分为两种情况,一种是靠y轴切出去,另一种是靠X轴切出去。
import java.util.*; public class Main{ public static void main(String [] args){ Scanner scan = new Scanner(System.in); int t = scan.nextInt(); for(int i=0;i<t;i++){ int begin = scan.nextInt(); int n = scan.nextInt(); Cut(begin,n); } } public static void Cut(int begin,int n){ if(begin<n){ System.out.println((n-begin)*begin); } else if(begin>n){ System.out.println(n*n/8); } else System.out.println("Error"); } }
这里稍微补充一下,往x轴切,面积的最大值应该怎么算?
假设其中两条边为a,另一条边为b,那么可以列出等式,面积.
也就是。这就是一个倒着的一元二次函数,当 ,S有最大值
我的题解B
- AC了
如果,不能往y轴切,就往x轴切。()
如果,既能往y轴切,也能往x轴切,就两个都计算,再取最大值。
public static void Cut(int begin,int n){ int c1 = 0; if(begin<n){ c1 = (n-begin)*begin; } int c2 = n*n/8>c1?n*n/8:c1; System.out.println(c2); }
再补充一下,我对一楼的理解。
以一个测试用例展开
期望输入 | 期望输出 |
---|---|
86 11 | 15 |
一看这个测试用例就知道,要往X轴切,但是有两条边的边长到底应该取什么呢?
楼主把那条边设为 ,但是11/4,等于2.75,但C++会进行向下取整,所以l等于2。那么算出来的面积为
但是,有没有考虑过向上取整,把l变成3。这时候的面积为
但是我发现 取整的这个操作可以留到求面值那一步,直接,取整的事情,留给最后一步。如这里,然后取整到15.