Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:题解

Posted by 2018207181 at 2020-01-31 11:25:59 on Problem 3273
In Reply To:题解 Posted by:dingyaguang117 at 2010-09-05 01:38:00
> 题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份都是连续的天),要求每份的和尽量少,输出这个和。
> 
>     一开始二分的上界为n天花费的总和(相当于分成1份),下界为每天花费的最大值(相当于分成n份),然后二分,每次的mid值为(上界 + 下界)/ 2,然后根据mid值遍历n天花费,对n天的花费进行累加,每当超过mid值 份数++,看看这个mid值能把n天分成几份,如果份数大于m,表示mid偏小,下界 = mid + 1,反之小于等于mid,上界 = mid - 1,然后输出最后的mid值即可,复杂度为 O(nlogM),M约为第一次的上界。
> 
>  

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator