题目

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
1≤T≤100
1≤N≤105
1≤K≤105
1≤ai≤105

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

题解

比较直观的思路题

有多个不同大小的方块
有以下操作:

  1. 对于 相邻 的方块,可以将他们融合成一个
  2. 对于一个方块,可以将它拆成任意大小的两个

然后将所有方块分成等大小的 k 个方块,求最少的操作步数

首先,显然: 如果平均数不是整数肯定是不可能有结果的
同理,平均数是整数,最终必定能得到结果

由于操作必然是相邻的方块,因此如果要求最短的步数,应该把多出来的部分传到尽可能近的位置

由于方块本身是等价的,因此对于不同的方块,只需要将其往后传递即可
只需要将判断当前方块与平均值大小,如果大于就拆成平均值和多余部分,继续这一操作;如果小于就和下一个方块融为一个

上面的思路其实瞬间就能得到,但是第一次写 WA 了

有一点要特别注意,由于方块体积和数量最大都是 105
因此,极端情况会有 1010
int 存不下！！！

换了 long long 就 A 了

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <vector>
#include <list>
#include <map>
#include <functional>

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 >> T;
    while(T--) {
        int n,m;
        cin >> n >> m;

        long long sum = 0;
        for(int i = 0;i<n;i++) {
            cin >> a[i];
            sum += a[i];
        }

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