ArcSoft's Office Rearrangement
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1133 Accepted Submission(s): 428
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
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1133 Accepted Submission(s): 428
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
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
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
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
分析：
本题其实很简单，如果使用标记把长度固定为Sum的区间等分成K份，那么不仅每等分的长度bolck是固定(即bolck=Sum/K)，其标记的位置也是固定的，第i(0<=1<=K-1)个标记在坐标轴上的位置为i*bolck,那么这样一来，我们将输入的每块区间长度转换为坐标轴上的坐标，例如"2 3 4"就变成了"2 5 9"。
由于最后在给定总长度和块数之后，等分的标记点也就确定了，那么在最终的数轴上，如果一开始我们转换的点是的最终的标记点，就不需要变动，如果不是，就删除(这里就相当于了合并操作),最后再检查下是不是所有标记点都存在，不是的话就不断添加标记点，保证最终由K-1个标记点(这里相当于划分间隔操作)。
源码如下:
#include<cstdio>
typedef long long ll;
ll arr[100005];
int main()
{int T;scanf("%d", &T);for(int t=1;t<=T;t++){ll N,K,sum=0,res=0;ll temp;scanf("%lld%lld", &N, &K);for(int i=0;i<N;i++){scanf("%lld", &temp);sum+=temp;arr[i]=sum;}if(sum%K!=0){
// cout<<"Case #"<<t<<": -1"<<endl;printf("Case #%d: -1\n", t);continue;}ll block=sum/K;int pos=0;for(int i=1;i<=K;i++){while(arr[pos]<i*block){pos++;res++;}if(arr[pos]!=i*block && i!=K)res++;else pos++;}//cout<<"Case #"<<t<<": "<<res<<endl;printf("Case #%d: %lld\n", t, res);}return 0;
}PS：这里尤其要注意变量的范围,1≤N≤10^5且1≤ ai≤10^5,那么最终求得的最大坐标范围sum是在1<=Max<=10^10，这样的话，是超过了int的范围，所以要使用long long类型。因为这个原因改了好几次，坑啊～