1335 - Beijing Guards
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=4081
Beijing was once surrounded by four rings of city walls: the Forbidden City Wall, the Imperial City Wall, the Inner City Wall, and finally the Outer City Wall. Most of these walls were demolished in the 50s and 60s to make way for roads. The walls were protected
by guard towers, and there was a guard living in each tower. The wall can be considered to be a large ring, where every guard tower has exaetly two neighbors.
The guard had to keep an eye on his section of the wall all day, so he had to stay in the tower. This is a very boring job, thus it is important to keep the guards motivated. The best way to motivate a guard is to give him lots of awards. There are several
different types of awards that can be given: the Distinguished Service Award, the Nicest Uniform Award, the Master Guard Award, the Superior Eyesight Award, etc. The Central Department of City Guards determined how many awards have to be given to each of the
guards. An award can be given to more than one guard. However, you have to pay attention to one thing: you should not give the same award to two neighbors, since a guard cannot be proud of his award if his neighbor already has this award. The task is to write
a program that determines how many different types of awards are required to keep all the guards motivated.
The input contains several blocks of test eases. Each case begins with a line containing a single integerln100000,
the number of guard towers. The next n lines correspond to then guards: each line contains an integer, the number of awards the guard requires. Each guard requires at least 1, and at most
l00000 awards. Guardi and
i + 1 are neighbors, they cannot receive the same award. The first guard and the last guard are also neighbors.
The input is terminated by a block with n = 0.
For each test case, you have to output a line containing a single integer, the minimum numberx of award types that allows us to motivate the guards. That is, if we havex types of awards,
then we can give as many awards to each guard as he requires, and we can do it in such a way that the same type of award is not given to neighboring guards. A guard can receive only one award from each type.
3
4
2
2
5
2
2
2
2
2
5
1
1
1
1
1
0
8
5
3
思路:
1 当n为偶数的时候,ans = max(r[i]+r[i+1]),可以自己画个图验证;
2 当n为奇数的时候就不满足了,那么我们可以利用二分答案然后判断从而求出最小值。假设有p种礼物,那么设第一个人的礼物为1~r1,那么不难发现最有的分配的策略一定是这样的:除1以外的其他人,编号为偶数的人尽量往前取,编号为奇数的人尽量往后取。这样我们只要最后判断第n个人是否与第一个人有冲突即可。
3 由于题目并没有要我们输出实际的方案,那么我们只需要记录每个人在[1,r1]和[r1+1,n]这个范围内取了几个,最后判断第n个人是否有取[1,r1]范围内的数即可。
4 注意对于n = 1的情况需要特判。
完整代码:
/*0.059s*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, r[maxn], ll[maxn], rr[maxn];
/// 测试p个礼物是否足够。
/// ll[i]是第i个人拿到的“左边的礼物”总数,rr[i]类似
bool test(int p)
{
int x = r[1], y = p - r[1];
ll[1] = x, rr[1] = 0;
for (int i = 2; i <= n; i++)
{
if (i & 1)
{
///因为要满足二者,所以要取最小值
rr[i] = min(y - rr[i - 1], r[i]); /// 尽量拿右边的礼物
ll[i] = r[i] - rr[i];
}
else
{
ll[i] = min(x - ll[i - 1], r[i]); /// 尽量拿左边的礼物
rr[i] = r[i] - ll[i];
}
}
return ll[n] == 0;
}
int main()
{
while (scanf("%d", &n), n)
{
for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
if (n == 1) /// 特判n=1
{
printf("%d\n", r[1]);
continue;
}
r[n + 1] = r[1];
int L = 0, R = 0;
for (int i = 1; i <= n; i++) L = max(L, r[i] + r[i + 1]);///最小范围
if (n & 1)
{
for (int i = 1; i <= n; i++) R = max(R, r[i] * 3);///注意3倍最大范围
while (L < R)
{
int M = L + (R - L) / 2;
if (test(M)) R = M;
else L = M + 1;
}
}
printf("%d\n", L);
}
return 0;
}
分享到:
相关推荐
CERC SATA 2S控制器RAID创建手册,Adaptec SATA HostRAID Controller 手册,Dell Precision WorkStation 470
CERC SATA 2S 可选择阵列级别:RAID 0, RAID 1 本手册包括 A RAID 0的创建 B RAID 1的创建 C 管理阵列(包括查看阵列信息,校验硬盘,删除阵列,重建阵列)
认识人的特性 职业价值关系 职业定位规划 关键职业素养
CERC-P-aacraid-RHEL4Gold-1.1.5.2392-A01.tar.gz
(换句话说,如果x,y都在该区间中,那么所有介于x,y之间的数也在该区间中)现在有m(1 ≤ n, m ≤ 100000)个询问,每个询问给出一个区间[xi,
dell2850server2003 RAID驱动64位2850
由不同数据表示类型的交易量指标。
牛圈养 2015年中欧区域竞赛的“母牛禁闭”问题解决方案
The Economist Intelligence Unit is a specialist publisher serving companies establishing and managing operations across national borders. For 60 years it has been a source of information on business ...
Dell PERC 5, PERC 6 and CERC 6 RAID Controller Device Driver for Windows Server 2003 x86 This is the driver for following family of PowerEdge Expandable RAID Controller: PERC 5 Controllers PERC 6...
该脚本使用 CERC、Bayram 等人获得沿岸沉积物运输。 和 Kamphuis 方程。 CERC 方程使用不同的 K 值。 使用命令窗口给出所有输入参数。 输入: rho = 水的质量密度,kg/m3 rhos = 沉积物的质量密度,kg/m3 poro = ...
该项目是通过。 运行开发服务器 ... loanAPY(在复合货币中也称为BorrowAPY)合约:cToken(cETH / CERC20)方法:roweRatePerBlock() 设置日志级别 localStorage.setItem('loglevel:filda','DEBUG')
珠江口磨刀门输沙率估算,陈丽芳,,根据波能流法,采用代表波方法确定波要素,运用CERC和SMB公式,以及海港水文规范和夏都公式对磨刀门海域的沿岸输沙率进行了计算。�
实验03:李斯特塞里尼(Cerințe): Creati o lista-直接在ordonata中,在utils.h中定义的datele(valori intregi... Jocul Lui Joseph:在cerc中的所有复制品(un pilar un un numar si un nume asociat)。 Primul