畜栏预定 有 $N$ 头牛在畜栏中吃草。 每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。 给定 $N$ 头牛和每头牛开始吃草的时间 $A$ 以及结束吃草的时间 $B$,每头牛在 $[A,B]$ 这一时间段内都会一直吃草。 当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。 求需要的最小畜栏数目和每头牛对应的畜栏方案。 输入格式第 $1$ 行:输入一个整数 $N 2022-09-25 算法 算法 贪心
防晒 有 $C$ 头奶牛进行日光浴,第 $i$ 头奶牛需要 $minSPF[i]$ 到 $maxSPF[i]$ 单位强度之间的阳光。 每头奶牛在日光浴前必须涂防晒霜,防晒霜有 $L$ 种,涂上第 $i$ 种之后,身体接收到的阳光强度就会稳定为 $SPF[i]$,第 $i$ 种防晒霜有 $cover[i]$ 瓶。 求最多可以满足多少头奶牛进行日光浴。 输入格式第一行输入整数 $C$ 和 $L$。 接下来的 2022-09-25 算法 算法 贪心
天才ACM 天才ACM给定一个整数 $M$,对于任意一个整数集合 $S$,定义“校验值”如下: 从集合 $S$ 中取出 $M$ 对数(即 $2×M$ 个数,不能重复使用集合中的数,如果 $S$ 中的整数不够 $M$ 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 $S$ 的“校验值”。 现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。 我们要把 $A$ 分成若 2022-07-15 算法 算法 归并排序 二分 倍增
奇数码问题 奇数码问题你一定玩过八数码游戏,它实际上是在一个 $3×3$ 的网格中进行的,$1$ 个空格和 $1∼8$ 这 $8$ 个数字恰好不重不漏地分布在这 $3×3$ 的网格中。 例如: 1235 2 81 3 _4 6 7 在游戏过程中,可以把空格与其上、下、左、右四个方向之一的数字交换(如果存在)。 例如在上例中,空格可与左、上、下面的数字交换,分别变成: 1235 2 8 5 2 _ 2022-07-04 算法 算法 逆序对 归并排序 有解性判定
超快速排序 超快速排序在这个问题中,您必须分析特定的排序算法—-超快速排序。 该算法通过交换两个相邻的序列元素来处理 $n$ 个不同整数的序列,直到序列按升序排序。 对于输入序列 9 1 0 5 4,超快速排序生成输出 0 1 4 5 9。 您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。 输入格式输入包括一些测试用例。 每个测试用例的第一行输入整数 $n$,代表该用例中输入序列的长 2022-07-02 算法 算法 逆序对 归并排序
动态中位数 动态中位数依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。 输入格式第一行输入一个整数 $P$,代表后面数据集的个数,接下来若干行输入各个数据集。 每个数据集的第一行首先输入一个代表数据集的编号的整数。 然后输入一个整数 $M$,代表数据集中包含数据的个数,$M$ 一定为奇数,数据之间用空格隔开。 数据集的剩余行由数据集的数据构成,每行包含 $10$ 个数 2022-07-02 算法 算法 堆
七夕祭 七夕祭七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。 于是 TYVJ 今年举办了一次线下七夕祭。 Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕,于是他们决定去 TYVJ 七夕祭游玩。 TYVJ 七夕祭和 11 区的夏祭的形式很像。 矩形的祭典会场由 $N$ 排 $M$ 列共计 $N×M$ 个摊点组成。 虽然摊点种类繁多,不过 cl 只对其中的一部分摊点感兴趣,比如章鱼烧、苹果糖、棉 2022-06-30 算法 算法 前缀和 中位数
货仓选址 货仓选址在一条数轴上有 $N$ 家商店,它们的坐标分别为 $A_1…A_N$。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。 为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。 输入格式 第一行输入整数$N$。 第二行$N$个整数$A_1…A_N$。 输出格式 输出一个整数,表示距离之和的最小值。 数据范围 $1≤N≤100000$ 输入样例 124 2022-01-16 算法 算法 中位数
电影 电影莫斯科正在举办一个大型国际会议,有 $n$ 个来自不同国家的科学家参会。 每个科学家都只懂得一种语言。 为了方便起见,我们把世界上的所有语言用 $1$ 到 $10^9$ 之间的整数编号。 在会议结束后,所有的科学家决定一起去看场电影放松一下。 他们去的电影院里一共有 $m$ 部电影正在上映,每部电影的语音和字幕都采用不同的语言。 对于观影的科学家来说,如果能听懂电影的语音,他就会很开心;如果能 2022-01-15 算法 算法 二分 离散化
最佳牛围栏 最佳牛围栏农夫约翰的农场由 $N$ 块田地组成,每块地里都有一定数量的牛,其数量不会少于 $1$ 头,也不会超过 $2000$ 头。 约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包含 $F$ 块地,其中 $F$ 会在输入中给出。 在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。 输入格式 第一行输 2022-01-11 算法 算法 前缀和 二分