# 二分

Acwing257 关押罪犯

原题链接:Acwing257

题目描述:S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为1~N。

他们之间的关系自然也极不和谐。

很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。

如果两名怨气值为 c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为 c 的冲突事件。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到 S 城 Z 市长那里。

公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。

他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少?

……

READ MORE

Acwing1165 单词环

原题链接:Acwing1165

题目描述:我们有 n 个字符串,每个字符串都是由 a∼z 的小写英文字母组成的。

如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配,那么我们称 A 与 B 能够相连(注意:A 能与 B 相连不代表 B 能与 A 相连)。

我们希望从给定的字符串中找出一些,使得它们首尾相连形成一个环串(一个串首尾相连也算),我们想要使这个环串的平均长度最大。

……

READ MORE

Acwing361 观光奶牛

原题链接:Acwing361

题目描述:给定一张 L 个点、 P 条边的有向图,每个点都有一个权值 $f[i]$,每条边都有一个权值 $t[i]$。

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意:数据保证至少存在一个环。

……

READ MORE

Acwing244 谜一样的牛

原题链接:Acwing244

题目大意:有$n$头奶牛,已知它们的身高为 $1$~$n$ 且各不相同,但不知道每头奶牛的具体身高。现在这$n$头奶牛站成一列,已知第$i$头牛前面有$A_i$头牛比它低,求每头奶牛的身高。

……

READ MORE

Codeforces772A Voltage Keepsake

原题链接:Codeforces772A

题目大意:有$n$个设备,第$i$个每秒耗电$a_i$, 初始状态电量$b_i$。另有一个充电器,每秒给设备能充电$p$。 不计切换用电设备和切换充电器充电对象的时间,问最多可以连续使用所有的用电设备的最大时间是多少。

……

READ MORE

Recents
Categories
Tags
Links