Gotta Write A Code

C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理

posts - 33, comments - 33, trackbacks - 0

<

2011年9月

>

日

一

二

三

四

五

六

28

29

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

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

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 閱讀(1532) 評論(1) 編輯收藏引用所屬分類: 算法題解

Feedback

# re: Poj 3104 二分答案

2011-11-09 16:39 | 小木

請教博主的如何讓代碼可以縮進的回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。


相關文章: hdu 2087 hud 1686 hdu 2896 多模式串匹配2 hdu 2222 多模式串匹配水題兩道 zoj 3542 poj 3074 逆序數及其求法 Poj 3310 判環(huán)+度 Poj 3104 二分答案 Poj1111 水題

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品