小蓝与钥匙
问题描述
小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了 一个游戏。
小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房 间对应一把钥匙, 每把钥匙只能打开自己的门。现在小蓝让这 28 个孩子分别将 自己宿舍的钥匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 28!=28×27×⋯×128!=28×27×⋯×1 种分配方案。小蓝想知道这些方案中, 有多少种方案恰有 一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙, 有 14 个孩子分到的不是自己房间的钥匙)。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
分析:记一下全错排列的公式吧
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a =14;
long n1 = 28;
long m = 14;
System.out.println(C(n1,m)*D(a));
}
//全错排列 错位的14把
static long D(long a){
if(a==0||a==1){
return 0;
}
else if(a==2){
return 1;
}
else{
return (a-1)*(D(a-2)+D(a-1));
}
}
//组合C 14 28
static long C(long n,long m){
long res = 1L;
for(int i = 0;i<m;i++){
res = res*(n-i)/(i+1);
}
return res;
}
}
火柴棒数字
问题描述
小蓝最近迷上了用火柴棒拼数字字符, 方法如下图所示:
他只能拼 0 至 9 这十种数字字符, 其中每个数字字符需要的火柴棒的数目 依次是: 6,2,5,5,4,5,6,3,7,66,2,5,5,4,5,6,3,7,6 。他不喜欢重复拼同一个数字字符, 所以对于每个 数字字符他最多拼十个。小蓝会把拼出来的数字字符组合在一起形成一个整数, 例如对于整数 345 , 需要的火柴棒的数目为 5+4+5=145+4+5=14 根。小蓝有 300 根 火柴棒, 他想知道自己能拼出的最大整数是多少? 可以不使用完这 300 根火柴 棒, 可以有多余的火柴棒剩下。
答案提交
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
分析:先考虑位数,消耗相同火柴时选择数字大的,然后直接可算出来
import java.util.*;
public class Main {
public static void main(String[] args) {
System.out.println("9999999999777777777755555555554444444444333333333322222222221111111111");
}
}内存管理
问题描述
小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。
为了简化问题, 变量的类型只有以下三种:
int: 整型变量, 一个 int 型变量占用 4 Byte 的内存空间。
long: 长整型变量, 一个 long 型变量占用 8 Byte 的内存空间。
String: 字符串变量, 占用空间和字符串长度有关, 设字符串长度为 LL, 则字符串占用 LL Byte 的内存空间, 如果字符串长度为 0 则占用 0 Byte 的内存 空间。
定义变量的语句只有两种形式, 第一种形式为:
type varl=value 1 , var2=value ⋯⋯;
定义了若干个 type 类型变量 var1、var2、 ⋯⋯, 并且用 value1、value2 ⋯⋯ 初始化,
多个变量之间用'， 分隔, 语句以';' 结尾, type 可能是 int、long 或 String。例如 int a=1,b=5,c=6a=1,b=5,c=6 ；占用空间为 12 Byte; long a=1,b=5a=1,b=5 ； 占用空间为 16 Byte; String s1=′′′,s2=′′s1=′′′,s2=′′ hello"， 3=′′3=′′ world"；占用空 间为 10 Byte。
第二种形式为:
type[] arr1=new type[size1], arr2=new type[size2] ⋯⋯;
定义了若干 type 类型的一维数组变量 arr1arr2⋯arr1arr2⋯, 且数组的大小为 size1、size2 ⋯⋯, 多个变量之间用'，'进行分隔, 语句以';' 结尾, type 只可 能是 int 或 long。例如 int[] a1=new int[10]；占用的内存空间为 40。
Byte; long [] a1=new long [10]， a2=new long [10]；占用的内存空间为 160 Byte。
已知小蓝有 TT 条定义变量的语句, 请你帮他统计下一共占用了多少内 存空间。结果的表示方式为: a GB b MB c KB d Ba GB b MB c KB d B, 其中 a、b、c、da、b、c、d 为统计的 结果, GB、MB、KB、BGB、MB、KB、B 为单位。优先用大的单位来表示, 1 GB=1024MB1 GB=1024MB， 1MB=1024 KB,1 KB=1024 B1MB=1024 KB,1 KB=1024 B, 其中 BB 表示 Byte。如果 a、b、c、da、b、c、d 中的某几个 数字为 0 , 那么不必输出这几个数字及其单位。题目保证一行中只有一句定义 变量的语句, 且每条语句都满足题干中描述的定义格式, 所有的变量名都是合 法的且均不重复。题目中的数据很规整, 和上述给出的例子类似, 除了类型后 面有一个空格, 以及定义数组时 new 后面的一个空格之外, 不会出现多余的空格。
输入格式
输入的第一行包含一个整数 TT, 表示有 TT 句变量定义的语句。 接下来 TT 行, 每行包含一句变量定义语句。
输出格式
输出一行包含一个字符串, 表示所有语句所占用空间的总大小。
分析:主要是考字符串api的使用吧感觉,答案从网上摘录优化了的.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
scan.nextLine();
long totalSize = 0;
for (int j = 0; j < T; j++) {
String[] s = scan.nextLine().split(" ");
String type = s[0];
if (type.equals("int") || type.equals("long")) {
int size = type.equals("int") ? 4 : 8;
String[] varNames = s[1].split(",");
totalSize += size * varNames.length;
} else if (type.equals("String")) {
String[] varNames = s[1].split(",");
for (String v : varNames) {
int l = v.indexOf("\"");
int r = v.lastIndexOf("\"");
totalSize += (r - l - 1);
}
} else if (type.equals("int[]") || type.equals("long[]")) {
int sizePerElement = type.equals("int[]") ? 4 : 8;
for (int i = 2; i < s.length; i++) {
int l = s[i].indexOf("[");
int r = s[i].indexOf("]");
int length = Integer.parseInt(s[i].substring(l + 1, r));
totalSize += sizePerElement * length;
}
}
}
// 计算GB, MB, KB, B
long gb = totalSize / (1024L * 1024L * 1024L);
long mb = (totalSize % (1024L * 1024L * 1024L)) / (1024L * 1024L);
long kb = (totalSize % (1024L * 1024L)) / 1024L;
long b = totalSize % 1024L;
StringBuilder sb = new StringBuilder();
if (gb != 0) sb.append(gb).append("GB");
if (mb != 0) sb.append(mb).append("MB");
if (kb != 0) sb.append(kb).append("KB");
if (b != 0 || totalSize == 0) sb.append(b).append("B");
System.out.println(sb.toString());
scan.close();
}
}选素数
问题描述
小蓝有一个数 xx, 每次操作小蓝会选择一个小于 xx 的素数 pp, 然后在 xx 成 为 pp 的倍数前不断将 xx 加 1 , (如果 xx 一开始就是 pp 的倍数则 xx 不变)。
小乔看到了小蓝进行了 2 次上述操作后得到的结果 nn, 他想知道 xx 在一开 始是多少。如果有多种可能, 他想知道 xx 一开始最小可以是多少, 而如果不存 在任何解, 说明小乔看错了, 此时请输出 −1−1 。
输入格式
输入一行包含一个整数 nn, 表示经过两次操作后 xx 的值。
输出格式
输出一行包含一个整数表示 xx 的初始值。如果有多个解, 输出最小的。如 果不存在解, 请输出 −1−1 。
分析:答案来自网络,每次操作后x是p的倍数,最小的prev_x还原回去就减去一个p再加一,即假设x为np,prev_x即为(n-1)p+1.
import java.util.Scanner;
public class Main {
static boolean is_prime(int n)
{
if(n <= 1) return false;
for(int i = 2;i <= n / i;i++)
if(n % i == 0) return false;
return true;
}
static int lpf(int n)//计算最大质因数
{
int ans = 2;
for(int i = 2; i <= n / i;i++)
{
while(n % i == 0)
{
ans = i;
n /= i;
}
}
if(n > 1) return n;
return ans;
}
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int x = scanner.nextInt();
if(is_prime(x)) {
System.out.println(-1);
}else {
int z = lpf(x);
int l = x - z + 1;
int ans = (int)2e6;
for(int i = l;i <= x;i++) {
if(is_prime(i)) continue;
ans = Math.min(ans,i - lpf(i) + 1);
}
System.out.println(ans);
}
}
}括号序列树
问题描述
有一棵二叉树, 根结点上有一个空字符串, 每个点的左儿子上的字符串为 其父亲结点的字符串尾部额外加一个左括号, 右儿子则是在尾部加一个右括号。 树中的每个叶子结点上的字符串都分别和每个由 nn 对括号组成的合法括号序列一一对应。
给定 nn, 求此时这棵树的最大匹配所含的边数。
输入格式
输入一行包含一个整数 nn 。
输出格式
输出一行包含一个整数表示满足条件的序列的数量, 答案可能很大, 请输 出答案除以 998244353 的余数。
分析:不会,从网上摘了个答案
import java.util.Scanner;
public class Main {
static int MOD = 998244353;
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
init(n);
int ans = 0;
for (int i = 0; i < n; i++) {// 满二叉树,奇数层节点个数
ans = (ans + C(2 * i + 1, i)) % MOD;
}
for (int i = (n + 1) / 2; i < n; i++) {// 不是满二叉树,需要减去一部分
ans = (ans - C(2 * i + 1, 2 * i - n)) % MOD;
}
System.out.println((ans + MOD) % MOD);
}
static int C(int n, int m) {
return (int) ((long) factorial[n] * inverse[m] % MOD * inverse[n - m] % MOD);
}
static int N = 2000001;
static int[] factorial = new int[N], inverse = new int[N];//fac[i]=i!, facinv[i]为i!在模p下的逆元
/**
预处理出阶乘数组和乘法逆元数组
*/
static void init(int n) {
factorial[0] = 1;
for (int i = 1; i <= 2 * n; i++) {//求阶乘
factorial[i] = (int) ((long) factorial[i - 1] * i % MOD);
}
inverse[2 * n] = fastPow(factorial[2 * n]);
for (int i = 2 * n; i > 0; i--) {//倒序递推求逆元
inverse[i - 1] = (int) ((long) inverse[i] * i % MOD);
}
}
/**
快速幂求逆元,base^(MOD-2)
*/
private static int fastPow(int base) {
int ans = 1;
int p = MOD - 2;
while (p > 0) {
if ((p & 1) == 1) ans = (int) ((long) ans * base % MOD);
base = (int) ((long) base * base % MOD);
p >>= 1;
}
return ans;
}
}斐波那契数组
问题描述
如果数组 A=(a0,a1,⋯,an−1)A=(a0,a1,⋯,an−1) 满足以下条件, 就说它是一个斐波那契数 组:
n≥2n≥2;
a0=a1a0=a1
对于所有的 i(i≥2)i(i≥2), 都满足 ai=ai−1+ai−2ai=ai−1+ai−2 。
现在, 给出一个数组 AA, 你可以执行任意次修改, 每次修改将数组中的某 个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组 AA 会变成一个斐波那契数组。
输入格式
输入的第一行包含一个整数 nn, 表示数组 AA 中的元素个数。
第二行包含 nn 个整数 a0,a1,⋯,an−1a0,a1,⋯,an−1, 相邻两个整数之间用一个空格分隔。
输出格式
输出一行包含一个整数表示最少需要修改数组 AA 中的几个元素之后, 数组 AA 可以变为一个斐波那契数组。
分析:从头生成相同数目的斐波那契数列s,如果A是斐波那契数列那么一定可以由s*k倍生成
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int f1 = 1, f2 = 1;
int[] d = new int[(int) 1e6 + 1];
int max = 0;
for (int i = 1; i <= n; i++) {
int x = sc.nextInt();
if (x % f1 == 0) {
d[x / f1]++;
max = Math.max(max, d[x / f1]);
}
int temp = f1 + f2;
f1 = f2;
f2 = temp;
}
System.out.println(n - max);
}
}数组个数
问题描述
小蓝有一个长度为 nn 的数组 B=(b0,b1,⋯,bn−1)B=(b0,b1,⋯,bn−1), 数组 BB 是由另一个长度 为 nn 的环形数组 A=(a0,a1,⋯,an−1)A=(a0,a1,⋯,an−1) 经过一次相邻最大化操作得到的, 其中 aiai 与 ai+1ai+1 相邻, a0a0 与 an−1an−1 相邻。
形式化描述为:
bi={max(an−1,a0,a1),(i=0); max(ai−1,ai,ai+1),(0<i<n−1); max(an−2,an−1,a0),(i=n−1).bi={max(an−1,a0,a1),(i=0); max(ai−1,ai,ai+1),(0<i<n−1); max(an−2,an−1,a0),(i=n−1).
小蓝想知道, 可能有多少个满足条件的数组 AA, 经过一次相邻最大化操作 后能得到数组 BB, 注意 AA 中的每个元素都要求为非负整数。
输入格式
输入的第一行包含一个整数 nn, 表示数组长度。
第二行包含 nn 个整数 b0,b1,⋯,bn−1b0,b1,⋯,bn−1, 相邻两个整数之间用一个空格分隔。
输出格式
输出一行包含一个整数表示答案, 答案可能很大, 请输出答案除以 1000000007 后的余数。
分析:看注释
import java.util.*;
public class Main {
// 定义模数，用于结果取模防止溢出
public static int mod = (int)(1e9 + 7);
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // 读取数组长度
int[] a = new int[n + 1]; // 存储输入的数组B（题目中的b数组）
for(int i = 0; i < n; i ++)
a[i] = scan.nextInt(); // 读取数组B的每个元素
// DP数组：dp[k][x][y]表示处理到第k个位置时，A[k-1]=x且A[k]=y的方案数
long[][][] dp = new long[n + 1][15][15]; // 15是为了包含0-10的取值
long res = 0; // 存储最终结果
// 枚举所有可能的A[0]和A[1]的取值（i和j从0到10）
for(int i = 0; i <= 10; i ++) {
for (int j = 0; j <= 10; j++) {
// 清空DP数组（每次枚举新的i,j时重置）
for(int k = 0; k < n; k ++)
for(int l = 0; l <= 10; l ++)
for(int m = 0; m <= 10; m ++)
dp[k][l][m] = 0;
// 初始化：A[0]=i, A[1]=j的方案数为1
dp[1][i][j] = 1;
// 动态规划填充DP数组（从第2个位置开始到第n-1个位置）
for (int k = 2; k < n; k++) {
for (int x = 0; x <= 10; x++) // A[k-2]的取值
for (int y = 0; y <= 10; y++) { // A[k-1]的取值
if (dp[k - 1][x][y] == 0) continue; // 跳过无效状态
// 枚举A[k]的可能取值z
for (int z = 0; z <= 10; z++) {
if (k == n - 1) { // 处理最后一个位置的特殊情况（环形数组）
// 需要满足三个条件：
// 1. max(A[k-2], A[k-1], A[k]) = B[k-1]
// 2. max(A[k], A[0], A[1]) = B[0]（环形）
// 3. max(A[k], A[k-1], A[0]) = B[n-1]（环形）
if (Math.max(x, Math.max(y, z)) == a[k - 1]
&& Math.max(z, Math.max(i, j)) == a[0]
&& Math.max(z, Math.max(y, i)) == a[n - 1]) {
dp[k][y][z] += dp[k - 1][x][y]; // 更新DP值
dp[k][y][z] %= mod; // 取模
}
} else { // 非最后一个位置
// 只需满足max(A[k-2], A[k-1], A[k]) = B[k-1]
if (Math.max(x, Math.max(y, z)) == a[k - 1]) {
dp[k][y][z] += dp[k - 1][x][y]; // 更新DP值
dp[k][y][z] %= mod; // 取模
}
}
}
}
}
// 统计所有可能的A[n-2]和A[n-1]的取值对应的方案数
for(int k = 0; k <= 10; k ++)
for(int l = 0; l <= 10; l ++)
res = (res + dp[n - 1][k][l]) % mod; // 累加到结果并取模
}
}
System.out.println(res); // 输出结果
scan.close(); // 关闭Scanner
}
}六六大顺
问题描述
六六大顺, 本指农历六月初六。多用于祝福中年人士家庭幸福, 工作顺利, 事业有成, 身体健康。源自《左传》“君义, 臣行, 父慈, 子孝, 兄爱, 弟敬, 此数者累谓六顺也。”
6 在我国自古以来是一个吉祥的数字, 定义数列 A=(a1,a2,⋯,ai,⋯)A=(a1,a2,⋯,ai,⋯), 其中 a1=6,a2=66,⋯,ai=10⋅ai−1+6a1=6,a2=66,⋯,ai=10⋅ai−1+6 。
定义一个数列 B=(b1,b2,⋯,bi,⋯)B=(b1,b2,⋯,bi,⋯), 其中 b1=6×6,b2=66×66,⋯b1=6×6,b2=66×66,⋯, bi=ai⋅aibi=ai⋅ai 。
现在小蓝想知道数列 BB 的前 nn 项的和是多少, 你能帮邦小蓝吗?
输入格式
输入一行包含一个正整数 nn 。
输出格式
输出一行包含一个整数表示数列 BB 前 nn 项的和
不会
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
StringBuffer answer = new StringBuffer();
int count_3 = 0;
int count_4 = 0;
int count_5 = 0;
int current;
int remainder;
int all;
current = 6 * n;
answer.append(current % 10);
remainder = current / 10;
int i;
for (i = 1; i < 2 * n; i++) {
all = n - i / 2;
count_3 = i <= n ? 1 : 0;
count_4 = (i - 1) / 2;
count_4 = count_4 <= all ? count_4 : all;
count_5 = all - count_3 - count_4;
current = 3 * count_3 + 4 * count_4 +5 * count_5 + remainder;
answer.append(current % 10);
remainder = current / 10;
}
while (remainder > 0) {
answer.append(remainder % 10);
remainder /= 10;
}
scan.close();
System.out.println(answer.reverse());
}
}交通信号
问题描述
LQLQ 市的交通系统可以看成由 nn 个结点和 mm 条有向边组成的有向图。在每 条边上有一个信号灯, 会不断按绿黄红黄绿黄红黄... 的顺序循环 (初始时刚好 变到绿灯)。当信号灯为绿灯时允许正向通行, 红灯时允许反向通行, 黄灯时不 允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立, 其中黄灯的 持续时长等同于走完路径的耗时。当走到一条边上时, 需要观察边上的信号灯, 如果允许通行则可以通过此边, 在通行过程中不再受信号灯的影响; 否则需要 等待, 直到允许通行。
请问从结点 ss 到结点 tt 所需的最短时间是多少, 如果 ss 无法到达 tt 则输出 −1−1
输入格式
输入的第一行包含四个整数 n,m,s,tn,m,s,t, 相邻两个整数之间用一个空格分隔。
接下来 mm 行, 每行包含五个整数 ui,vi,gi,ri,diui,vi,gi,ri,di, 相邻两个整数之间用一个 空格分隔, 分别表示一条边的起点, 终点, 绿灯、红灯的持续时长和距离 (黄 灯的持续时长)。
输出格式
输出一行包含一个整数表示从结点 ss 到达 tt 所需的最短时间。
分析:一个很细节的处理反向边,等待时间的考虑很复杂,贴的是网上一个很细的代码
1. 信号灯周期计算（核心中的核心！）
每个路口的信号周期分为4个阶段：
绿灯亮（持续
g秒）→ 可直接通过黄灯亮（持续
d秒）→ 下个是红灯，必须等待红灯亮（持续
r秒）→ 禁止通行黄灯亮（持续
d秒）→ 下个是绿灯，必须等待
完整周期时长 = g + d + r + d = g + r + 2d
2. 到达时间与信号灯状态判断（最烧脑部分）
假设你在tt秒到达某个路口：
情况1：
tt % T < g→ 当前是绿灯，无需等待情况2：
g ≤ tt % T < g+d→ 当前黄灯且下个是红灯，需等待(g+d) - (tt%T)情况3：
g+d ≤ tt % T < g+d+r→ 当前红灯，需等待T - (tt%T) + g情况4：
g+d+r ≤ tt % T < T→ 当前黄灯且下个是绿灯，需等待T - (tt%T)
注：
T是完整周期，tt%T表示在当前周期中的时间点
import java.util.*;
// 特殊的dijkstra
// dijkstra是每个选取最小的，如果弹出的节点已径扩展过了，就continue
// 然后扩展每个点计算经过该点的最短路径,如果小于就原最短路径，则入堆
// 这里特殊的边权值是动态变化的
// tt < g 则当前路口为绿灯
// g < tt < g + d 则当前路口为黄灯且下一个灯为红灯
// g + d < tt < g + d + r 则当前路口为红灯
// g + d + r < tt < g + 2d + r 则当前路口为黄灯且下一个灯为绿灯
public class Main {
static final int N = 1000010, M = 4 * N;
static int[] h = new int[N], e = new int[M], ne = new int[M], g = new int[M], r = new int[M], d = new int[M], f = new int[M];
static long[] times = new long[N];
static int idx = 0;
static void add(int a, int b, int green, int red, int dist, int flag) {
e[idx] = b; g[idx] = green; r[idx] = red;
d[idx] = dist; ne[idx] = h[a]; f[idx] = flag; h[a] = idx++;
}
static long dijkstra(int n, int m, int s, int t) {
Arrays.fill(times, Long.MAX_VALUE);
times[s] = 0;
PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> Long.compare(a.dist,b.dist));
pq.offer(new Pair(s, 0));
while (!pq.isEmpty()) {
Pair pair = pq.poll();
int u = pair.node;
long dist = pair.dist;
if (dist > times[u]) continue;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
long gr = g[i], re = r[i], di = d[i], fl = f[i];
long tot = gr + re + 2 * di;
long curt = dist % tot;
if (fl == 1) curt = curt >= gr ? tot - curt : 0;
else curt = curt >= gr + di && curt < gr + di + re ? 0 : curt < gr + di ? gr + di - curt : tot - curt + gr + di;
long newDist = dist + curt + di;
if (newDist < times[j]) {
times[j] = newDist;
pq.offer(new Pair(j, newDist));
}
}
}
return times[t] > Long.MAX_VALUE / 2 ? -1 : times[t];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(),m = scanner.nextInt();
int s = scanner.nextInt(),t = scanner.nextInt();
Arrays.fill(h, -1);
for (int i = 0; i < m; i++) {
int a = scanner.nextInt(), b = scanner.nextInt();
int green = scanner.nextInt(),red = scanner.nextInt();
int dist = scanner.nextInt();
add(a, b, green, red, dist, 1); add(b, a, green, red, dist, 0);
}
System.out.println(dijkstra(n, m, s, t));
}
static class Pair {
private final int node;
private final long dist;
public Pair(int node, long dist) {
this.node = node;
this.dist = dist;
}
}
}图书借阅
问题描述
小蓝是一所图书馆的管理员, 图书馆中目前有 nn 种书, 第 ii 种书有 aiai 本。
小蓝目前有 mm 条末来若干天中用户的预约借阅记录, 每个借阅记录由 bi,li,ribi,li,ri 组成, 表示在 lili 日要借用一本书 bi,ribi,ri 日归还, riri 日结束后图书馆才可 以将这本书重新借出。
小蓝分析了一下预约借阅记录, 发现现有的书不一定能满足所有人的预约 请求, 于是小蓝打算额外购买一些书加入到图书馆。小蓝的预算有限, 请问如 果额外添加不超过 xx 本书, 最多有多少条预约记录能得到满足? 小蓝可以选取 一部分记录使其满足, 不一定需要按借阅或预定的时间顺序满足。
输入格式
输入的第一行包含三个整数 n,m,xn,m,x ，相邻两个整数之间用一个空格分隔。
第二行包含 nn 个整数 a1,a2,⋯,ana1,a2,⋯,an, 相邻两个整数之间用一个空格分隔, 表 示目前拥有的每种书的本数。
接下来 mm 行, 每行包含 3 个整数 bi,li,ribi,li,ri, 相邻两个整数之间用一个空格分 隔, 表示一条预约借阅记录。
输出格式
输出一行包含一个整数表示给定条件下最多能满足预约借阅的记录数。
分析:对每本书的预约记录进行处理，记录每个区间可以满足多少个预约记录。有多少个不同的区间则需要多少本库存。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 书的种类数
int m = sc.nextInt(); // 预约数
int s = sc.nextInt(); // 限制的最大区间数
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 读入预约信息
List<List<int[]>> b = new ArrayList<>();
for (int i = 0; i < n; i++) {
b.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int bookIndex = sc.nextInt() - 1;
int j = sc.nextInt();
int k = sc.nextInt();
b.get(bookIndex).add(new int[]{j, k});
}
long ans = 0;
List<Long> cnt = new ArrayList<>();
// 处理每本书的预约
for (int i = 0; i < n; i++) {
List<int[]> list = b.get(i);
list.sort(Comparator.comparingInt(o -> o[0])); // 按开始时间排序
PriorityQueue<int[]> h = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
for (int[] x : list) {
int xStart = x[0];
int y = x[1];
if (!h.isEmpty() && h.peek()[0] < xStart) {
// 合并
int[] top = h.poll();
// 替换堆中的元素
h.offer(new int[]{y, top[1] + 1});
} else {
// 新添加
h.offer(new int[]{y, 1});
}
}
// 收集当前书的堆中的信息
List<Long> res = new ArrayList<>();
while (!h.isEmpty()) {
int[] item = h.poll();
res.add((long) item[1]);
}
// 排序倒序
res.sort(Comparator.reverseOrder());
// 扩展cnt
int limit = a[i];
for (int j = limit; j < res.size(); j++) {
cnt.add((long) res.get(j));
}
for (int j = 0; j < Math.min(limit, res.size()); j++) {
ans += res.get(j);
}
}
// 继续贪心地添加cnt中的元素
cnt.sort(Comparator.reverseOrder());
int i = 0;
while (s > 0 && i < cnt.size()) {
ans += cnt.get(i);
i++;
s--;
}
System.out.println(ans);
}
}