hdu 5933 ArcSoft’s Office Rearrangement(贪心)

Problem Description
ArcSoft, Inc. is a leading global professional computer photography and computer vision technology company.

There are N working blocks in ArcSoft company, which form a straight line. The CEO of ArcSoft thinks that every block should have equal number of employees, so he wants to re-arrange the current blocks into K new blocks by the following two operations:

– merge two neighbor blocks into a new block, and the new block’s size is the sum of two old blocks’.
– split one block into two new blocks, and you can assign the size of each block, but the sum should be equal to the old block.

Now the CEO wants to know the minimum operations to re-arrange current blocks into K block with equal size, please help him.

 

Input
First line contains an integer T, which indicates the number of test cases.

Every test case begins with one line which two integers N and K, which is the number of old blocks and new blocks.

The second line contains N numbers a1, a2, , aN, indicating the size of current blocks.

Limits
1T100
1N105
1K105
1ai105

 

Output
For every test case, you should output ‘Case #x: y’, where x indicates the case number and counts from 1 and y is the minimum operations.

If the CEO can’t re-arrange K new blocks with equal size, y equals -1.

 

Sample Input
3
1 3
14
3 1
2 3 4
3 6
1 2 3
Sample Output
Case #1: -1
Case #2: 2
Case #3: 3
无解的话求一遍和看是不是k的倍数即可。
然后现在计算如何得到最小解。首先如果有解的话,那么肯定次可以。相当于把n个数用n-1次合并起来,再分成k堆,需要k-1次。设平均值。我们可以想象如果有x个数的和为need的倍数,那么这k个数在我们刚刚的策略中是合并了x次(这x个数之间一共x-1次,合并完全后在和别的数合并1次),分了次,然而实际上并不需要,因为多合并了一次,也多分裂了一次。所以我们只需要记录有多少组这样的x(前缀和搞出来)就可以了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注