（C++）HDU-5933——均分（贪心算法）

系统管理员 2021-12-03 05:01 263阅读 0赞

### 题目描述 ###

有n个数，对于这n个数，每次只能执行下面两种操作其中的一种：  
一：将相邻的两个数相加合并成一个数，  
二：将一个数分成相邻的两个数，这两个数的和仍然等于之前的数  
请问至少需要多少次操作才能将这n个数变成k个相等的数。

#### *input* ####

第一行是一个数t，代表有t组样例。（1≤T≤100）  
每组样例的第一行是两个数n （1≤n≤10^5和 k(1≤k≤10^5)  
接下来一行是n个数a0,a1,a2…an-1

#### *output* ####

对于每组样例，输出的格式是 ‘Case \#x: y’，x代表这是第几个case,从1开始，y是最少的操作次数，  
如果不能将这n个数变成相等的k个数，则y为-1.

### 题目解析 ###

题目要求操作数最小，那么使用贪心的思想：使每一次分离操作都可以得到一或多个最终所要得到的那个平均数。

*  这样考虑的话，我们对所给的数进行遍历，如果当前的数大于或等于平均数，则分出平均数，将剩下的加到下一个数据上。
 *  如果当前的数小于平均数则直接将这个数加到下一个数上

*注意：该题的数据范围较大，将所有的数加到一起时，会超出 int 型的表示范围，所以应使用 long long 类型来保存数据*

### 源代码（可AC） ###

#include<iostream>
    #include<stdio.h>
    using namespace std;
    long long a[100010];
    int main()
    {
        
        long long t,x=0;
        scanf("%lld",&t);
        while(t--)
        {
        
            x++;
            long long n,k,ans=0,m;
            long long sum=0;
            scanf("%lld%lld",&n,&k);
            for(int i=0;i<n;++i)
            {
        
                scanf("%d",&a[i]);
                sum+=a[i];
            }
            if(sum%k!=0)
                cout<<"Case #"<<x<<": "<<-1<<endl;
            else
            {
        
                long long avg=sum/k;
                for(int i=0;i<n;++i)
                {
        
                    if(a[i]>=avg)
                    {
        
                        ans+=a[i]/avg;
                        m=a[i]%avg;
                        if(m==0)
                            ans--;
                        else
                        {
        
                            a[i+1]+=m;
                            ans++;
                        }
                    }
                    else
                    {
        
                        a[i+1]+=a[i];
                        ans++;
                    }
                }
                cout<<"Case #"<<x<<": "<<ans<<endl;
            }
        }
    }