<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
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:
<ul>
<li>merge two neighbor blocks into a new block, and the new block's size is the sum of two old blocks'.</li>
<li>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.</li>
</ul>
Now the CEO wants to know the minimum operations to re-arrange current blocks into K block with equal size, please help him.
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
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 
1≤T≤100 
1≤N≤105 
1≤K≤105 
1≤ai≤105
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
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.
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
3 
1 3 
14 
3 1 
2 3 4 
3 6 
1 2 3
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
Case #1: -1 
Case #2: 2 
Case #3: 3
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
比较直观的思路题
有多个不同大小的方块 
有以下操作:
<ol>
<li>对于 相邻 的方块,可以将他们融合成一个</li>
<li>对于一个方块,可以将它拆成任意大小的两个</li>
</ol>
然后将所有方块分成等大小的 k 个方块,求最少的操作步数
<hr>
首先,显然: 如果平均数不是整数肯定是不可能有结果的 
同理,平均数是整数,最终必定能得到结果
由于操作必然是相邻的方块,因此如果要求最短的步数,应该把多出来的部分传到尽可能近的位置
由于方块本身是等价的,因此对于不同的方块,只需要将其往后传递即可 
只需要将判断当前方块与平均值大小,如果大于就拆成平均值和多余部分,继续这一操作;如果小于就和下一个方块融为一个
<hr>
上面的思路其实瞬间就能得到,但是第一次写 WA 了
有一点要特别注意,由于方块体积和数量最大都是 105 
因此,极端情况会有 1010 
int 存不下！！！
换了 <code>long long</code> 就 A 了
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;iomanip&gt;
#include &lt;string&gt;
#include &lt;cstring&gt;
#include &lt;stack&gt;
#include &lt;queue&gt;
#include &lt;cmath&gt;
#include &lt;set&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;map&gt;
#include &lt;functional&gt;

using namespace std;

const int maxn = 100005;

int kase = 1;
long long a[maxn];

int main() {
 cin.tie(0);
 cin.sync_with_stdio(false);

 int T;
 cin &gt;&gt; T;
 while(T--) {
 int n,m;
 cin &gt;&gt; n &gt;&gt; m;

 long long sum = 0;
 for(int i = 0;i&lt;n;i++) {
 cin &gt;&gt; a[i];
 sum += a[i];
 }

 cout &lt;&lt; &#34;Case #&#34; &lt;&lt; kase++ &lt;&lt; &#34;: &#34;;
 if(sum%m) {
 cout &lt;&lt; &#34;-1&#34;;
 } else {
 long long t = sum / m;
 long long ans = 0;
 for(int i = 0;i&lt;n;i++) {
 while(a[i]&gt;t) {
 a[i] -= t;
 ans++;
 }
 if(a[i]&lt;t) {
 a[i + 1] += a[i];
 ans++;
 }
 }
 cout &lt;&lt; ans;
 }
 cout &lt;&lt; endl;
 }
 return 0;
}
</pre>

HDU 5933.ArcSoft's Office Rearrangement(2016 CCPC 杭州 A)