CF1027C Minimum Value Rectangle

之前做的时候没想出来...现在来数学推导一波。

题意:从n个木棒中选出4个拼成一个矩形,使得 (周长)2/面积 最小。

解:设矩形宽a长b。我们要最小化下面这个式子:

CF1027C Minimum Value Rectangle

去掉常数,不妨设b = a + len,则化为下式:

CF1027C Minimum Value Rectangle

取倒数,也就是最大化下式:

CF1027C Minimum Value Rectangle

显然对于每个确定的a,len越小越好。所以直接取相邻的即可。

好像还有一种推导方法......

原式可直接化为a/b + b/a,这就是个耐克函数双钩函数,让a/b趋近1也就是a=b,所以a和b越接近越好。

上一篇:HDU 1264 Counting Squares (线段树-扫描线-矩形面积并)


下一篇:codeforces_Codeforces Round #541 (Div. 2)_abc