HDU 4923 (杭电多校 #6 1003题)Room and Moor(公式+栈)

题目地址:HDU 4923

比赛的时候脑残了。。思路完全想出来了。。只不过想出了个根本不可能存在的极端数据,然后一看输入数据是100组,就把自己给否决了。。。sad。。当时就应该大胆试一试的。。。

这个题首先可以把最前面的0和最后面的1去掉,因为这两块总可以用0和1抵消掉。然后中间就分成了10相间的情况,然后根据10相间,可以分成若干组,每一组都是由几个1和几个0组成的。比如说1101101110,就可以分成110,110,1110这样的三组。

然后这时候可以可以对每一组内只取一个数来使得这组的和最小。那应该怎么找这个数呢。假设这组有a个1,b个0,取的数为X,就可以列出式子(a+b)x^2-2*a*x+a,对他求导得知当x为a/(a+b)的时候最小。所以这一段应该取a/(a+b).

然后剩下的只有一个任务了,怎么让某些组合在一块保证所取得这个数是递增的。为了方便,可以弄一个栈。然后当栈为空的时候就放进去。遍历这些组。当该组的x比栈顶的x小,这组就跟前面的那组合并,并把栈顶的弹出。合并完后的值继续与栈顶的比较,直到栈为空或者栈顶的x比该组的x小,再放入栈。如果一上来就比栈顶的大,那就直接放入栈。

最后,由于每组取的值都是a/(a+b),可以代入列出的式子。求得最终的值是(a*b)/(a+b)。可以直接利用这个值来计算。

注意中间过程可能会爆int,要用int64。代码如下:

#include #include #include #include #include using namespace std; __int64 a[110000], b[110000]; struct node { __int64 l, r, sum, a; double z; }q[110000]; int main() { __int64 t, n, i, j, pos1, pos2, cnt, flag; double ans; scanf("%I64d",&t); while(t--) { stackQ; scanf("%I64d",&n); for(i=0;i=0;i--) { if(a[i]==0) { pos2=i+1; break; } } flag=0; cnt=0; int b=0, c=0; for(i=pos1;i!=pos2;) { b=0; c=0; q[cnt].l=i; while(a[i]==1) { i++; b++; } while(a[i]==0&&i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:矩阵经典题目八:hdu 2175 How many ways??
下一篇:poj3671Dining Cows(DP)
相关文章

UVA 1555 - Garland(推公式,贪心)

POJ 1265 多边形格点数Pick公式

1到N的平方和公式

SRM 626 D1L1: FixedDiceGameDiv1,

编程算法 - 圆圈中最后剩下的数字(递

HDU 4869 Turn the pokers(思维+

hdu1018--斯特灵公式

codeforces #259 DIV2 C题 Little

HDU 4952 Number Transformation(

HDU 4950 Monster(公式)

图文推荐

HDU 4923 (杭电多校 #6 1003题)Room and Moor(公式+栈)
ZOJ 3640 Help Me
HDU 4923 (杭电多校 #6 1003题)Room and Moor(公式+栈)
CF 518C(Anya and
HDU 4923 (杭电多校 #6 1003题)Room and Moor(公式+栈)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-06 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.093 (s). 10 q(s)