HDU-5933-ArcSoft's Office Rearrangement

ACM模版

描述

题解

给定 NN 个数要求划分为 KK 份,一共有两种操作,一种是将相邻两数合并,一种是将一个数拆开两部分。

很明显的贪心模拟,这场比赛好像比较钟爱贪心模拟,可是这个题好坑,因为题目中约定的数据不可能超过 intint,却挂了,必须使用 longlonglong long 才行。

代码

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 10;

long long N, K;
long long a[MAXN];
queue<long long> qi;

int main()
{
    int T;
    scanf("%d", &T);

    for (int case_ = 1; case_ <= T; case_++)
    {
        printf("Case #%d: ", case_);

        scanf("%lld%lld", &N, &K);

        long long sum = 0;
        for (int i = 0; i < N; i++)
        {
            scanf("%lld", a + i);
            sum += a[i];
        }

        if (sum % K)
        {
            puts("-1");
            continue;
        }

        while (!qi.empty())
        {
            qi.pop();
        }

        long long ans = 0, unit = sum / K, t;
        for (int i = 0; i < N; i++)
        {
            if (!qi.empty())
            {
                t = qi.front();
                qi.pop();
                a[i] += t;
                ans++;
            }

            if (a[i] > unit)
            {
                t = a[i] / unit;
                ans += t;
                t = a[i] % unit;
                if (t)
                {
                    qi.push(t);
                }
                else
                {
                    ans--;
                }
            }
            else if (a[i] < unit)
            {
                qi.push(a[i]);
            }
        }

        printf("%lld\n", ans);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JackeyGao的博客

Django小技巧22: 设计一个好的模型

本篇将分享一些技巧,用户改进 Model 的设计。其中有很多与命名约定有关, 这可以大大的提高代码的可读性。

17020
来自专栏大内老A

基于CallContextInitializer的WCF扩展导致的严重问题

WCF是一个具有极高扩展度的分布式通信框架,无论是在信道层(Channel Layer)还是服务模型层(Service Model),我们都可以自定义相关组件通...

22790
来自专栏jeremy的技术点滴

解决dubbo导致tomcat无法优雅shutdown的问题

57940
来自专栏java一日一条

Guava - EventBus(事件总线)

Guava在guava-libraries中为我们提供了事件总线EventBus库,它是事件发布订阅模式的实现,让我们能在领域驱动设计(DDD)中以事件的弱引用...

18020
来自专栏机器学习从入门到成神

java.lang.StackOverflowError异常解决

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1.8K20
来自专栏joycl

c#面试题汇总

下面的参考解答只是帮助大家理解,不用背,面试题、笔试题千变万化,不要梦想着把题覆盖了,下面的题是供大家查漏补缺用的,真正的把这些题搞懂了,才能“以不变应万变”。...

61410
来自专栏蓝天

使用可重入函数进行更安全的信号处理

在早期的编程中,不可重入性对程序员并不构成威胁;函数不会有并发访问,也没有中断。在很多较老的 C 语言实现中,函数被认为是在单线程进程的环境中运行。

9420
来自专栏NetCore

.NET 4特性聚焦:代码契约

去年,我们已经开始在讨论Spec#,这是一个基于C#的支持通过契约来进行设计的语言。以契约来设计是构建于诸如静态类型化这样的概念之上的,特定的动作只有在编译时被...

26850
来自专栏大内老A

WCF技术剖析之二十五: 元数据(Metadata)架构体系全景展现[元数据描述篇]

在[WS标准篇]中我花了很大的篇幅介绍了WS-MEX以及与它相关的WS规范:WS-Policy、WS-Transfer和WSDL,因为WCF元数据结构体系完全是...

18480
来自专栏MasiMaro 的技术博文

ATL模板库中的OLEDB与ADO

上次将OLEDB的所有内容基本上都说完了,从之前的示例上来看OLEDB中有许多变量的定义,什么结果集对象、session对象、命令对象,还有各种缓冲等等,总体上...

15120

扫码关注云+社区

领取腾讯云代金券