UVA1335-- Beijing Guards_uva 1335-程序员宅基地

题意：有n个人围成一个圈，其中第i个人想要ri个不同的礼物。求最少需要多少种礼物，使得相邻的人的礼物都不相同。

思路：这是大白上面的一道贪心题目。想法挺好的。

首先如果n为偶数时，只要找出相邻两个人的r值最大，就是所需的最少的礼物数量。如果为奇数时，那情况就不一样了，因为当第1个和第n个都是奇数，按照上面的方法，他们的礼物种类是一样的，就不符合题意。那么我们可以按照第一个人所需要的礼物数量为基准划分区间。假设最坏情况下的礼物总数为R = max(ri) * 3，所以区间划分为【1，r1】，【r1 + 1，R】。所以只要记录每个人在这两个区间内取了几个，分别用front[i]，back[i]表示。最后在判断是否符合，也就是第n个人是否在【1，r1】内取礼物。注意特判n == 1时的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 100010;

int arr[MAXN], front[MAXN], back[MAXN];
int n;

int judge(int num) {
    int x = arr[1], y = num - arr[1];
    front[1] = x;
    back[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 1) {
            back[i] = min(y - back[i - 1], arr[i]); //尽量往后取
            front[i] = arr[i] - back[i]; 
        } 
        else {
            front[i] = min(x - front[i - 1], arr[i]); //尽量往前取
            back[i] = arr[i] - front[i];
        }  
    }
    return front[n] == 0; 
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= n; i++) 
            scanf("%d", &arr[i]);

        if (n == 1) {
            printf("%d\n", arr[1]);
            continue;  
        } 

        arr[n + 1] = arr[1]; 
        int L = 0, R = 0;
        for (int i = 1; i <= n; i++) 
            L = max(L, arr[i] + arr[i + 1]);

        memset(front, 0,sizeof(front));
        memset(back, 0,sizeof(back));
        if (n % 2 == 1) {
            for (int i = 1; i <= n; i++) 
                R = max(R, arr[i] * 3);
            while (L < R) {
                int mid = L + (R - L) / 2;
                if (judge(mid)) 
                    R = mid;
                else
                    L = mid + 1; 
            } 
        }
        printf("%d\n", L); 
    }
    return 0;
}

本文链接：https://blog.csdn.net/u011345461/article/details/38403329

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

pascal语言难还是python语言_lisp语言代替python_Lisp 语言优点那么多，为什么国内很少运用？...-程序员宅基地

文章浏览阅读140次。为什么Lisp没有流行起来本文探讨的是为什么Lisp语言不再被广泛使用的。很久以前，这种语言站在计算机科学研究的前沿，特别是人工智能的研究方面。现在，它很少被用到，这一切并不是因为古老,类似古老的语言却被广泛应用.其他类似的古老的语言有 FORTRAN, COBOL, LISP, BASIC, 和ALGOL 家族,这些语言的唯一不同之处在于,他们为谁设计,FORTRAN是为科学家和工程师设计的,他..._pascal 没有过时

进入 Tomcat 应用程序管理界面和部署Web应用_应用管理中心web页面-程序员宅基地

文章浏览阅读3.6k次，点赞2次，收藏9次。1 前言apache-tomcat-9.0.35我们都知道 Tomcat 可以部署 war包和静态资源，一般都是放在webapps下面；但是我们还应该知道，有个界面会帮我们去完成这个操作的，当然这个界面一般是不开放的，自己用的时候可以开放出来。开启 Tomcat服务（直接到tomcat服务器的bin目录下运行startup.sh脚本）；浏览器访问 http://localhost:8080 ，如图：上述就是Tomcat的三个控制台界面的入口按钮，分别是Server Status控_应用管理中心web页面

hive详解（一）_desc extended table_name; 解析-程序员宅基地

文章浏览阅读1.3k次。1、Hive简介 Hive是基于Hadoop的一个数据仓库工具，可以将结构化的数据文件映射成一张表，并提供类SQL查询功能。Hive是由Facebook开源用于解决海量结构化日志的数据统计的工具。在Hadoop生态系统中，HDFS用于存储数据，Yarn用于资源管理，MapReduce用于数据处理，而Hive是构建在Hadoop之上的数据仓库，包括以下方面：（1）使用HQL作..._desc extended table_name; 解析

愿码(ChainDesk.CN)：EOS钱包开发五使用cleos工具管理账号权限_账户权重之和须大于等于阀值-程序员宅基地

文章浏览阅读262次。在上一篇文章中，我们创建了一个新钱包并导入了一对公私钥，但是该钱包中并没有账号，在EOS区块链中创建账号是很扯蛋的事，必须使用已有的EOS账号才能创建新的EOS账号，使创建账号的时候便于扣费，因为创建的账号数据会占用区块链生产节点的内存资源，所以每创建一个EOS新账号都需要其他EOS账号消耗一定量的EOS来帮忙创建。那么我们找谁来创建呢？谁又有EOS账号呢？EOS主网中，最初始的EOS账号由E..._账户权重之和须大于等于阀值

python装饰器函数执行后日志_你必须学写 Python 装饰器的五个理由-程序员宅基地

文章浏览阅读42次。原标题：你必须学写 Python 装饰器的五个理由来源:Python程序员ID:pythonbuluo你必须学写Python装饰器的五个理由----装饰器能对你所写的代码产生极大的正面作用作者：Aaron Maxwell，2016年5月5日Python装饰器是很容易使用的。任何一个会写Python函数的人都能够学会使用装饰器，比如下面这个：@somedecoratordefsome_functio..._写一个类装饰器每次调对象就写入日志

户外汽车充电站的限流保护-程序员宅基地

文章浏览阅读489次，点赞9次，收藏7次。ASCP系列电气防火限流式保护器是安科瑞专门为了保护低压配电线路中短路、过载等问题研发，可以有效克服传统断路器、空气开关和监控设备存在的短路电流大、切断短路电流时间长、短路时产生的电弧火花大，以及使用寿命短等弊端，当发生短路故障时，能以微秒级速度快速限制短路电流以实现灭弧保护，从而能显著减少电气火灾事故，保障使用场所人员和财产的安全。交流充电桩采用符合国标的交流充电模式，输出功率高 7kW，一般车辆电池从 0 到充满需要 5~8 小时，具体情况视不同车型动力电池容量及实际充电功率而定。

随便推点

Unity下平面反射实现_unity 平面反射-程序员宅基地

文章浏览阅读6.2k次，点赞5次，收藏21次。平面反射通常指的是在镜子或者光滑地面的反射效果上，如下图所示，上图是一个光滑的平面，平面上的物体在平面上有对称的投影。一、平面反射的原理对于光照射到物体表面然后发生完美镜面反射的示意图，如下所示，对于平面反射，假设平面上任意一点都会发生完美的镜面反射。因此，眼睛看到物体的一点的反射信息是从反射向量处得到的，这个可以用下图来表示，这个实际上相当于，眼睛从平面的下面看向反射向量，如下图所示，因此，如上图所示，我们可以把摄像机根据平面对称变换到A点所示的位置，然后再渲染一遍场景到RenderT_unity 平面反射