# 差分约束

Acwing368 银河

原题链接:Acwing368

题目描述:银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。

我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是 $1$。

现在对于 $N$ 颗我们关注的恒星,有 $M$ 对亮度之间的相对关系已经判明。

你的任务就是求出这 $N$ 颗恒星的亮度值总和至少有多大。

……

READ MORE

Acwing1170排队布局

原题链接:Acwing1170

题目描述:当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。

农夫约翰有 N 头奶牛,编号从 1 到 N,沿一条直线站着等候喂食。

奶牛排在队伍中的顺序和它们的编号是相同的。

因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。

如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数 L。

另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数 D。

给出 $M_L$ 条关于两头奶牛间有好感的描述,再给出 $M_D$ 条关于两头奶牛间存有反感的描述。

你的工作是:如果不存在满足要求的方案,输出 -1;如果 1 号奶牛和 N 号奶牛间的距离可以任意大,输出 -2;否则,计算出在满足所有要求的情况下,1 号奶牛和 N 号奶牛间可能的最大距离。

……

READ MORE

Acwing393 雇佣收营员

原题链接:Acwing393

题目描述:一家超市要每天 24 小时营业,为了满足营业需求,需要雇佣一大批收银员。

已知不同时间段需要的收银员数量不同,为了能够雇佣尽可能少的人员,从而减少成本,这家超市的经理请你来帮忙出谋划策。

经理为你提供了一个各个时间段收银员最小需求数量的清单 R(0),R(1),R(2),…,R(23)。

R(0) 表示午夜 00:00 到凌晨 01:00 的最小需求数量,R(1) 表示凌晨 01:00 到凌晨 02:00 的最小需求数量,以此类推。

一共有N个合格的申请人申请岗位,第 i 个申请人可以从 $t_i$ 时刻开始连续工作 8 小时。

收银员之间不存在替换,一定会完整地工作 8 小时,收银台的数量一定足够。

现在给定你收银员的需求清单,请你计算最少需要雇佣多少名收银员。

……

READ MORE

Acwing362 区间

原题链接:Acwing362

题目描述:给定 $n$ 个区间 $[a_i,b_i]$ 和 $n$ 个整数 $c_i$。

你需要构造一个整数集合 $Z$,使得 $∀i∈[1,n]$, $Z$ 中满足 $a_i≤x≤b_i$ 的整数 $x$ 不少于 $c_i$ 个。

求这样的整数集合 $Z$ 最少包含多少个数。

……

READ MORE

Acwing1169 糖果

原题链接:Acwing1169

题目描述:幼儿园里有 N 个小朋友,老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候, 老师需要满足小朋友们的 K 个要求。

幼儿园的糖果总是有限的,老师想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

……

READ MORE

Recents
Categories
Tags
Links