当前位置：首页 > news >正文

AtCoder Weekday Contest 0004 Beta题解（AWC 0004 Beta A-E）

news 2026/5/11 22:10:11

A - Preparations Before Departure

【题目来源】

AtCoder：A - Preparations Before Departure

【题目描述】

Takahashi is preparing so that he won't be late for a meeting with his friend. Takahashi needs to finish several preparation tasks before leaving.
高桥正在做准备，以免与朋友见面时迟到。高桥需要在出发前完成几项准备工作。

To make it to the meeting on time, he must leave his house by \(T\) o'clock \(0\) minutes at the latest.
为了准时赴约，他必须在 \(T\) 点 \(0\) 分之前离开家。

Takahashi has \(N\) preparation tasks, and the \(i\)-th task takes \(A_i\) minutes to complete. Takahashi starts preparing at \(S\) o'clock \(0\) minutes on the same day, and performs each of the \(N\) tasks exactly once, consecutively without any breaks. The total time for all tasks is \(A_1 + A_2 + \cdots + A_N\) minutes.
高桥有 \(N\) 项准备工作，第 \(i\) 项任务需要 \(A_i\) 分钟完成。高桥在同一天 \(S\) 点 \(0\) 分开始准备，并按顺序连续执行这 \(N\) 项任务各一次，中间不休息。所有任务的总时长为 \(A_1 + A_2 + ⋯ + A_N\) 分钟。

If he finishes all preparations at or before \(T\) o'clock \(0\) minutes, Takahashi can leave in time for the meeting.
如果他在 \(T\) 点 \(0\) 分或之前完成所有准备工作，高桥就能及时离开去赴约。

Determine whether Takahashi can finish all preparations and leave by \(T\) o'clock \(0\) minutes.
判断高桥是否能在 \(T\) 点 \(0\) 分之前完成所有准备工作并离开。

【输入】

\(N\) \(S\) \(T\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

The first line contains three space-separated integers: \(N\), the number of preparation tasks; \(S\), the hour at which preparation starts; and \(T\), the hour of the departure deadline.
The second line contains space-separated integers \(A_1, A_2, \ldots, A_N\), representing the time (in minutes) each task takes.

【输出】

If Takahashi can finish all preparations and leave by \(T\) o'clock \(0\) minutes, print Yes; otherwise, print No.

【输入样例】

3 9 10
15 20 10

【输出样例】

Yes

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;int n, s, t;  // n: 题目数量，s: 考试开始时间(分钟)，t: 考试结束时间(分钟)
int sum;  // 总耗时int main()
{cin >> n >> s >> t;  // 读入题目数量和考试起止时间s = s * 60;  // 将开始时间转换为秒t = t * 60;  // 将结束时间转换为秒for (int i = 1; i <= n; i++){int x; cin >> x;  // 读入每道题需要的时间(秒)sum += x;  // 累加总耗时}// 判断从开始时间s开始，完成所有题目后是否超过结束时间tif (s + sum > t){cout << "No" << endl;  // 无法完成}else{cout << "Yes" << endl;  // 可以完成}return 0;
}

【运行结果】

3 9 10
15 20 10
Yes

B - Battery Level

【题目来源】

AtCoder：B - Battery Level

【题目描述】

Takahashi is developing a system to monitor the charging status of \(N\) smartphones.
高桥正在开发一个监控 \(N\) 部智能手机充电状态的系统。

At time \(0\), the battery level of each smartphone \(i\) (\(1 \leq i \leq N\)) is \(A_i\) mAh. Each smartphone \(i\) consumes battery at a constant rate of \(B_i\) mAh/s from time \(0\) onwards. However, the battery level does not go below \(0\) mAh.
在时刻 \(0\)，每部智能手机 \(i\)（\(1 ≤ i ≤ N\)）的电量为 \(A_i\) 毫安时。每部智能手机 \(i\) 从时刻 \(0\) 起以恒定速率 \(B_i\) 毫安时/秒消耗电量。但是，电量不会低于 \(0\) 毫安时。

That is, the battery level of smartphone \(i\) at time \(t\) (\(t \geq 0\)) is \(\max(A_i - B_i \times t,\ 0)\) mAh.
也就是说，智能手机 \(i\) 在时刻 \(t\)（\(t ≥ 0\)）的电量为 \(max(A_i - B_i × t, 0)\) 毫安时。

Find the total battery level of all \(N\) smartphones at time \(T\).
求在时刻 \(T\) 所有 \(N\) 部智能手机的总电量。

【输入】

\(N\) \(T\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
\(\vdots\)
\(A_N\) \(B_N\)

The first line contains an integer \(N\) representing the number of smartphones and an integer \(T\) representing the time at which to calculate the total battery level, separated by a space.
Lines \(2\) through \(N+1\) give the information for each smartphone.
Line \(1 + i\) contains an integer \(A_i\) representing the initial battery level of smartphone \(i\) and an integer \(B_i\) representing the battery consumption per second, separated by a space.

【输出】

Output the total battery level of all smartphones at time \(T\) as an integer on a single line.

【输入样例】

【输出样例】

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int n, t;  // n: 数据对数，t: 时间参数
int ans;  // 结果signed main()
{cin >> n >> t;  // 读入n和tfor (int i = 1; i <= n; i++){int a, b;  // a: 初始值，b: 衰减系数cin >> a >> b;  // 读入a和b// 计算max(0, a - b*t)，并累加到ansans += max(0ll, a - b * t);}cout << ans << endl;  // 输出结果return 0;
}

【运行结果】

C - Minimum Cost of Temperature Adjustment

【题目来源】

AtCoder：C - Minimum Cost of Temperature Adjustment

【题目描述】

Takahashi is going to conduct a chemistry experiment.
高桥将要进行一项化学实验。

In this experiment, he needs to process all \(N\) reagents, each exactly once. The processing temperature of reagent \(i\) \((1 \leq i \leq N)\) is \(H_i\) degrees.
在此实验中，他需要处理全部 \(N\) 种试剂，每种试剂恰好处理一次。试剂 \(i\)（\(1 ≤ i ≤ N\)）的处理温度为 \(H_i\) 度。

The temperature of the experimental apparatus is initially set to \(0\) degrees. To process a reagent, the apparatus temperature must be set to exactly match the processing temperature of that reagent. Takahashi can freely choose the order in which to process the reagents. After processing all reagents, he must return the apparatus temperature to \(0\) degrees to finish the experiment.
实验仪器的初始温度设定为 \(0\) 度。要处理一种试剂，仪器温度必须被设定为恰好匹配该试剂的处理温度。高桥可以自由选择处理试剂的顺序。处理完所有试剂后，他必须将仪器温度调回 \(0\) 度以结束实验。

When changing the apparatus temperature from \(a\) degrees to \(b\) degrees, the energy consumption is \(|a - b|\).
当将仪器温度从 \(a\) 度改变到 \(b\) 度时，能量消耗为 \(|a - b|\)。

If the order of processing the reagents is \((p_1, p_2, \ldots, p_N)\) (a permutation of \((1, 2, \ldots, N)\)), the total energy consumption is
如果处理试剂的顺序为 \((p_1, p_2, …, p_N)\)（即 \((1, 2, …, N)\) 的一个排列），则总能量消耗为

\[|H_{p_1}| + |H_{p_2} - H_{p_1}| + \cdots + |H_{p_N} - H_{p_{N-1}}| + |H_{p_N}| \]

Here, the first term corresponds to the cost of changing from the initial \(0\) degrees to the processing temperature of the first reagent, and the last term corresponds to the cost of returning from the processing temperature of the last reagent to \(0\) degrees.
此处，第一项对应于从初始 \(0\) 度改变到第一种试剂处理温度的成本，最后一项对应于从最后一种试剂的处理温度调回 \(0\) 度的成本。

Takahashi wants to minimize the total energy consumption by optimally choosing the order in which to process the reagents. Find the minimum total energy consumption.
高桥希望通过最优选择处理试剂的顺序来最小化总能量消耗。求最小总能量消耗。

【输入】

\(N\)
\(H_1\) \(H_2\) \(\cdots\) \(H_N\)

The first line contains an integer \(N\), representing the number of reagents.
The second line contains \(N\) integers \(H_1, H_2, \ldots, H_N\) separated by spaces, representing the processing temperature of each reagent.

【输出】

Output the minimum total energy consumption as an integer on a single line.

【输入样例】

3
5 -3 2

【输出样例】

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int n;  // 数据个数
int h[N], ans;  // h: 高度数组，ans: 总距离signed main()
{cin >> n;  // 读入数据个数for (int i = 1; i <= n; i++){cin >> h[i];  // 读入高度}sort(h + 1, h + n + 1);  // 对高度进行排序// 计算相邻元素间的绝对差值之和// 注意：这里循环到n+1，h[0]默认是0for (int i = 1; i <= n + 1; i++){ans += abs(h[i] - h[i - 1]);  // 累加绝对差值}cout << ans << endl;  // 输出总距离return 0;
}

【运行结果】

3
5 -3 2
16

D - Parking Lot Assignment

【题目来源】

AtCoder：D - Parking Lot Assignment

【题目描述】

Takahashi is developing a parking lot management system for a shopping mall. The parking lot has \(N\) parking spaces arranged in a row, numbered Space \(1\), Space \(2\), ..., Space \(N\) from the entrance side.
高桥正在为一家购物中心开发停车场管理系统。停车场有 \(N\) 个停车位排成一行，从入口侧起依次编号为车位 \(1\)、车位 \(2\)、……、车位 \(N\)。

Today, \(M\) cars are scheduled to visit, and all of these cars will use the parking lot during the same time period. The \(i\)-th car (\(1 \leq i \leq M\)) can park in any one of the consecutive parking spaces from Space \(L_i\) to Space \(R_i\).
今天有 \(M\) 辆车预约使用，且所有这些车将在同一时间段内使用停车场。第 \(i\) 辆车（\(1 \leq i \leq M\)）可以停在从车位 \(L_i\) 到车位 \(R_i\) 的任意一个连续停车位中。

Each car must be assigned exactly one parking space, and no parking space can be assigned to two or more cars.
每辆车必须被分配恰好一个停车位，且任何一个停车位都不能被分配给两辆或更多车辆。

If it is possible to assign a parking space to every car, output Yes; otherwise, output No.
如果可能为每辆车分配一个停车位，则输出 Yes；否则，输出 No。

【输入】

\(N\) \(M\)
\(L_1\) \(R_1\)
\(L_2\) \(R_2\)
\(\vdots\)
\(L_M\) \(R_M\)

The first line contains the number of parking spaces \(N\) and the number of arriving cars \(M\), separated by a space.
The \(i\)-th of the following \(M\) lines contains \(L_i\) and \(R_i\), representing the range of spaces where the \(i\)-th car can park, separated by a space.

【输出】

Print Yes on a single line if it is possible to assign a parking space to every car, or No if it is not possible.

【输入样例】

【输出样例】

Yes

【解题思路】

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;  // 定义最大数据范围
int n, m;              // n: 停车位数量, m: 车辆数量
struct Node            // 定义车辆数据结构
{int l, r;          // l: 可停最小位置, r: 可停最大位置
} a[N];
bool used[N];          // 标记停车位是否已被使用// 比较函数，用于排序车辆
// 优先按右端点r从小到大排序，右端点相同时按左端点l从小到大排序
bool cmp(Node x, Node y)
{if (x.r != y.r)    // 如果右端点不同return x.r < y.r;  // 按右端点升序排序return x.l < y.l;  // 右端点相同时，按左端点升序排序
}int main()
{// 读取输入数据cin >> n >> m;     // n: 停车位总数, m: 车辆总数// 读取每辆车的停车区间for (int i = 1; i <= m; i++)cin >> a[i].l >> a[i].r;  // 读取第i辆车的可停区间[l, r]// 对车辆按照排序规则进行排序// 排序后，右端点小的车辆优先处理，右端点相同时左端点小的优先sort(a + 1, a + m + 1, cmp);// 贪心算法分配停车位for (int i = 1; i <= m; i++)  // 遍历每一辆车{int j;  // 用于遍历可能的停车位置// 在当前车辆的可用区间[l, r]内寻找第一个空闲的停车位for (j = a[i].l; j <= a[i].r; j++){if (!used[j])          // 如果位置j未被使用{used[j] = true;    // 标记位置j为已使用break;             // 找到位置，跳出循环}}// 检查是否找到了合适的停车位// 如果j > a[i].r，说明在区间内没有找到空闲位置if (j > a[i].r){cout << "No" << endl;  // 无法为所有车辆分配停车位return 0;              // 程序结束}}// 如果所有车辆都成功分配到停车位cout << "Yes" << endl;         // 可以完成分配return 0;                       // 程序正常结束
}

【运行结果】