Gotta Write A Code
C++博客
::
首頁
::
新隨筆
::
聯系
::
聚合
::
管理
posts - 33, comments - 33, trackbacks - 0
<
2011年11月
>
日
一
二
三
四
五
六
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(5)
給我留言
查看公開留言
查看私人留言
隨筆分類
CUDA(1)
Windows Programming(4)
算法題解(22)
隨筆檔案
2012年5月 (1)
2012年3月 (9)
2011年11月 (4)
2011年10月 (1)
2011年9月 (1)
2011年7月 (1)
2011年6月 (3)
2011年5月 (1)
2011年4月 (1)
2011年3月 (2)
2011年1月 (2)
2010年12月 (1)
2010年11月 (6)
搜索
最新評論
1.?re: DX筆記[未登錄]
OrOrOrz!!
--diryboy
2.?re: 作品:動態語言AnyC 1.0
@so
其實里面的代碼存在bug...
--qqdy
3.?re: 作品:動態語言AnyC 1.0
游戲腳本高級編程的代碼很好啊。
--so
4.?re: 作品:動態語言AnyC 1.0
仰慕!!我剛開始學習編譯呢
--coreBugZJ
5.?re: AnyC:添加類型限制[未登錄]
Orz!!
--diryboy
閱讀排行榜
1.?逆序數及其求法(10800)
2.?Poj 3310 判環+度(5999)
3.?水文一篇--基于CUDA的矩陣相乘(4640)
4.?Poj2010 - 堆的應用(2497)
5.?水文:淺析PE File(2378)
評論排行榜
1.?作品:動態語言AnyC 1.0(4)
2.?poj 3074(3)
3.?ACM/ICPC杭州站 - hdu3680(3)
4.?水題四道 3-30(3)
5.?POJ Challenge - 2011.04.10部分題解(3)
Poj 3104 二分答案
題意:烘干機,給出一堆衣服的水分a[i],在不加烘干機情況下自動每一分鐘減少1水分,每分鐘可以變改衣服(i)到烘干機中,每分鐘減少k水分,求最少需要多少時間。
題解:第一時間就想到使用二分枚據答案+驗證這種思路,不過這題還是有些陷阱需要注意。
1. 驗證答案時,如果 a[i] <= mid,讓它自然烘干即可 ; 如果a[i] > mid,那么烘干這件衣服可以分成兩段時間:使用烘干機時間x1 + 自然烘干時間x2,那么可以列出等式:mid = x1 + x2; a[i] <= kx1+x2;于是得x1 >= (a[i] -mid)/(k-1);即得使用烘干機的最少時間x1
2.注意當k==1時,k-1 == 0,需要特殊處理,直接打出ans = maxV
3.注意當求left+right時,結果可能超出范圍,正確的方法應該是left + (right - left)*0.5;
#include
<
stdio.h
>
const
int
N
=
100005
;
int
n;
int
a[N];
int
k;
bool
check(
int
_value)
{
int
cnt
=
0
;
for
(
int
i
=
0
; i
<
n;
++
i)
{
if
(a[i]
>
_value)
{
double
kk
=
((
double
)(a[i]
-
_value))
/
(k
-
1
);
cnt
+=
(
int
)kk;
if
(kk
-
(
int
)kk
>
0
)
{
++
cnt;
}
if
(cnt
>
_value)
{
return
false
;
}
}
}
return
(cnt
<=
_value);
}
int
BinarySearch(
int
_low,
int
_high)
{
int
left
=
_low;
int
right
=
_high;
int
mid;
int
ans
=
_high;
while
(left
<=
right)
{
mid
=
(left
+
(right
-
left)
*
0.5
);
if
(check(mid))
{
ans
=
mid;
right
=
mid
-
1
;
}
else
{
left
=
mid
+
1
;
}
}
return
ans;
}
void
Test()
{
int
maxV
=
0
;
for
(
int
i
=
0
; i
<
n;
++
i)
{
scanf(
"
%d
"
,
&
a[i]);
if
(maxV
<
a[i])
{
maxV
=
a[i];
}
}
scanf(
"
%d
"
,
&
k);
if
(k
==
1
)
{
printf(
"
%d\n
"
,maxV);
}
else
printf(
"
%d\n
"
,BinarySearch(
0
,maxV));
}
int
main()
{
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
{
Test();
}
return
0
;
}
posted on 2011-11-09 12:45
bennycen
閱讀(1521)
評論(1)
編輯
收藏
引用
所屬分類:
算法題解
Feedback
#
re: Poj 3104 二分答案
2011-11-09 16:39 |
小木
請教博主的如何讓代碼可以縮進的
回復
更多評論
刷新評論列表
只有注冊用戶
登錄
后才能發表評論。
【推薦】100%開源!大型工業跨平臺軟件C++源碼提供,建模,組態!
相關文章:
hdu 2087 hud 1686
hdu 2896 多模式串匹配2
hdu 2222 多模式串匹配
水題兩道
zoj 3542
poj 3074
逆序數及其求法
Poj 3310 判環+度
Poj 3104 二分答案
Poj1111 水題
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Powered by:
C++博客
Copyright ©2025 bennycen
亚洲精品乱码久久久久久蜜桃不卡
|
久久久一本精品99久久精品66
|
久久国产福利免费
|
久久精品中文字幕一区
|
精品久久久久久久中文字幕
|
色诱久久av
|
久久国产精品无码一区二区三区
|
久久久久久久91精品免费观看
|
7777精品久久久大香线蕉
|
久久99国产精品一区二区
|
久久影视国产亚洲
|
成人久久精品一区二区三区
|
欧美精品丝袜久久久中文字幕
|
99久久精品国内
|
久久免费视频6
|
久久综合狠狠综合久久
|
国产福利电影一区二区三区久久久久成人精品综合
|
亚洲国产精品综合久久一线
|
天天躁日日躁狠狠久久
|
色婷婷综合久久久久中文字幕
|
97热久久免费频精品99
|
久久久无码精品亚洲日韩蜜臀浪潮
|
99久久精品毛片免费播放
|
97久久婷婷五月综合色d啪蜜芽
|
久久综合中文字幕
|
久久国产精品99国产精
|
午夜精品久久影院蜜桃
|
久久99精品国产麻豆蜜芽
|
国产精品久久久久影视不卡
|
伊人久久大香线蕉av一区
|
久久91这里精品国产2020
|
久久青草国产精品一区
|
久久精品中文闷骚内射
|
99久久国产精品免费一区二区
|
色偷偷91久久综合噜噜噜噜
|
久久免费大片
|
久久久久人妻一区精品
|
品成人欧美大片久久国产欧美...
|
精品久久久久久国产
|
一级做a爰片久久毛片人呢
|
久久99国产精品久久99
|