A - Optimal Practice Partner
【题目来源】
AtCoder：A - Optimal Practice Partner
【题目描述】
Takahashi is a member of the kendo club, and today he needs to choose an opponent for a practice match.
高桥是剑道俱乐部的一员，今天他需要为一场练习赛选择一个对手。
There are \(N\) members in the kendo club other than Takahashi, and each member has a skill value assigned to them. The members are numbered from \(1\) to \(N\), and the skill value of member \(i\) \((1 \leq i \leq N)\) is \(D_i\).
剑道俱乐部中除了高桥还有 \(N\) 名成员，每位成员都有一个技能值。成员编号从 \(1\) 到 \(N\)，成员 \(i\)（\(1 \leq i \leq N\)）的技能值为 \(D_i\)。
Takahashi's current skill value is \(L\). The condition for Takahashi to win a practice match against member \(i\) is that \(L \geq D_i\) holds. In other words, he can win if his skill value is greater than or equal to the opponent's skill value.
高桥当前的技能值为 \(L\)。高桥在练习赛中战胜成员 \(i\) 的条件是 \(L \geq D_i\) 成立。换句话说，如果他的技能值大于等于对手的技能值，他就能获胜。
The coach will recommend the "best practice partner for growth" to Takahashi. According to the coach's policy, practicing against the member who Takahashi can beat but whose skill is as close to his own as possible — that is, the member with the highest skill value among those he can beat — is expected to yield the maximum growth.
教练将向高桥推荐"最适合成长的最佳练习伙伴"。根据教练的政策，与高桥能够战胜但技能值尽可能接近他自己的成员——即在所有他能战胜的成员中技能值最高的成员——进行练习，预计能带来最大的成长。
Specifically, among the members satisfying \(L \geq D_i\), the member with the maximum \(D_i\) is recommended. If there are multiple such members, the one with the smallest member number is chosen.
具体来说，在满足 \(L \geq D_i\) 的成员中，选择 \(D_i\) 最大的成员进行推荐。如果有多个这样的成员，则选择编号最小的成员。
Find the number of the member recommended by the coach.
求教练推荐的成员编号。
However, if there is no member that Takahashi can beat, output -1.
但是，如果高桥无法战胜任何成员，则输出 -1。
【输入】
\(N\) \(L\)
\(D_1\) \(D_2\) \(\ldots\) \(D_N\)
- The first line contains an integer \(N\) representing the number of members other than Takahashi, and an integer \(L\) representing Takahashi's current skill value, separated by a space.
- The second line contains integers \(D_1, D_2, \ldots, D_N\) representing the skill values of each member, separated by spaces.
【输出】
Output the number of the member recommended by the coach in a single line. If there is no member that Takahashi can beat, output -1.
【输入样例】
5 10
3 14 10 7 10
【输出样例】
3
【算法标签】
模拟#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, l, maxn = -1, maxi = -1; // n: 数据个数, l: 阈值, maxn: 符合条件的最大值, maxi: 最大值对应的索引int main()
{cin >> n >> l; // 输入数据个数n和阈值l// 循环读取n个整数for (int i = 1; i <= n; i++){int x; // 当前读取的整数cin >> x;// 只考虑小于等于阈值l的数if (x <= l){// 如果当前数大于之前记录的最大值if (x > maxn){maxn = x; // 更新最大值maxi = i; // 更新最大值对应的位置索引}}}// 输出满足条件（≤l）的最大值的位置// 如果没有数满足条件（即maxi仍为-1），则输出-1cout << maxi << endl;return 0;
}
【运行结果】
5 10
3 14 10 7 10
3
B - Organizing the Locker
【题目来源】
AtCoder：B - Organizing the Locker
【题目描述】
Takahashi is in charge of managing \(N\) lockers in the school gymnasium. The lockers are numbered from \(1\) to \(N\). Initially, all lockers are closed.
高桥负责管理学校体育馆的 \(N\) 个储物柜。储物柜编号从 \(1\) 到 \(N\)。初始时，所有储物柜都是关闭的。
Takahashi will perform \(N\) operations. In the \(i\)-th operation (\(i = 1, 2, \ldots, N\)), for every locker whose number is a multiple of \(i\) (including locker number \(i\) itself), he toggles its state: if it is open, he closes it, and if it is closed, he opens it.
高桥将执行 \(N\) 次操作。在第 \(i\) 次操作中（\(i = 1, 2, \ldots, N\)），对于每个编号是 \(i\) 的倍数的储物柜（包括编号为 \(i\) 的储物柜本身），他会切换其状态：如果它是打开的，则关闭它；如果它是关闭的，则打开它。
For example, in the 1st operation, he toggles the state of all lockers whose numbers are multiples of \(1\), namely lockers \(1, 2, \ldots, N\). In the 2nd operation, he toggles the state of lockers whose numbers are multiples of \(2\) and at most \(N\), namely lockers \(2, 4, 6, \ldots\). In the 3rd operation, he toggles the state of lockers whose numbers are multiples of \(3\) and at most \(N\), namely lockers \(3, 6, 9, \ldots\).
例如，在第 1 次操作中，他会切换所有编号是 \(1\) 的倍数的储物柜的状态，即储物柜 \(1, 2, \ldots, N\)。在第 2 次操作中，他会切换编号是 \(2\) 的倍数且不超过 \(N\) 的储物柜的状态，即储物柜 \(2, 4, 6, \ldots\)。在第 3 次操作中，他会切换编号是 \(3\) 的倍数且不超过 \(N\) 的储物柜的状态，即储物柜 \(3, 6, 9, \ldots\)。
After all operations are completed, find the number of lockers that are open.
所有操作完成后，求处于打开状态的储物柜数量。
【输入】
\(N\)
An integer \(N\) representing the number of lockers is given on a single line.
【输出】
Print the number of lockers that are open after all operations are completed, as an integer on a single line.
【输入样例】
10
【输出样例】
3
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;signed main()
{cin >> n; // 输入n// 二分查找：寻找最大的整数x，使得x² ≤ nint l = 1, r = 1e9; // 二分查找的左右边界// 二分查找模板while (l < r){int mid = (l + r + 1) / 2; // 上取整，避免死循环if (mid * mid <= n) // 如果mid的平方小于等于nl = mid; // 说明mid可能太小，向右缩小范围else r = mid - 1; // 否则mid太大，向左缩小范围}cout << l << endl; // 输出结果：⌊√n⌋return 0;
}
【运行结果】
10
3
C - Seating Arrangement
【题目来源】
AtCoder：C - Seating Arrangement
【题目描述】
Takahashi is in charge of arranging \(N\) seats lined up in a row at a cultural festival venue. The seats are numbered \(1\) through \(N\) from left to right.
高桥负责安排文化节会场上一排 \(N\) 个座位的安排。座位从左到右编号为 \(1\) 到 \(N\)。
Currently, some seats are already occupied by guests. Specifically, seat \(i\) is occupied if \(S_i = 1\), and vacant if \(S_i = 0\).
目前，一些座位已经被客人占据。具体来说，如果 \(S_i = 1\)，则座位 \(i\) 已被占据；如果 \(S_i = 0\)，则座位 \(i\) 为空。
Takahashi can select \(0\) or more vacant seats as he likes and guide one new guest to each selected seat. However, he cannot move or remove guests who are already seated. Also, each seat can hold at most \(1\) person. Furthermore, due to the venue's ventilation rules, the following condition must be satisfied:
高桥可以任意选择 \(0\) 个或更多空座位，并引导一位新客人到每个选中的座位。但是，他不能移动或移除已经就坐的客人。同时，每个座位最多容纳 \(1\) 人。此外，由于会场的通风规定，必须满足以下条件：
- After all guests have been guided to their seats, there must be no three consecutive seats that are all occupied.
在所有客人被引导到座位后，不能存在三个连续的座位全部被占据。
In other words, if we denote the state of seat \(i\) after all guidance is complete as \(T_i\) (\(1\) if occupied, \(0\) if vacant), then for every \(i\) satisfying \(1 \leq i \leq N-2\), it must not be the case that \(T_i = T_{i+1} = T_{i+2} = 1\). It is guaranteed in the input that the initial state already satisfies this condition.
换句话说，如果用 \(T_i\) 表示引导完成后座位 \(i\) 的状态（\(1\) 表示被占据，\(0\) 表示空），那么对于每个满足 \(1 \leq i \leq N-2\) 的 \(i\)，不能有 \(T_i = T_{i+1} = T_{i+2} = 1\)。输入保证初始状态已满足此条件。
Takahashi wants to guide as many new guests as possible while satisfying this condition. Find the maximum number of new guests that can be guided.
高桥希望在满足此条件的情况下，引导尽可能多的新客人。求可以引导的新客人的最大数量。
【输入】
\(N\)
\(S_1\) \(S_2\) \(\ldots\) \(S_N\)
- The first line contains an integer \(N\) representing the number of seats.
- The second line contains \(N\) integers \(S_1, S_2, \ldots, S_N\) separated by spaces, representing whether each seat is occupied. \(S_i = 1\) means seat \(i\) is occupied, and \(S_i = 0\) means it is vacant.
【输出】
Print in one line the maximum number of new guests that can be guided while satisfying the condition.
【输入样例】
5
0 0 1 0 0
【输出样例】
2
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, ans;
int s[N]; // 整数数组，存储座位状态：0表示空，1表示已占int main()
{cin >> n; // 输入座位数量// 读取n个整数的座位状态for (int i = 1; i <= n; i++) {cin >> s[i];}// 遍历每个座位for (int i = 1; i <= n; i++) {if (s[i] == 1) // 如果当前座位已经有人，跳过{continue;}bool flag = true; // 标记当前座位是否可以安排新客人// 情况1：检查是否形成"1 0 1"的模式，即左右座位都有人if (i + 1 <= n && s[i - 1] == 1 && s[i + 1] == 1) {flag = false; // 不能安排，否则会形成"1 1 1"}// 情况2：检查左边是否已经有两个连续的1else if (i >= 3 && s[i - 2] == 1 && s[i - 1] == 1){flag = false; // 不能安排，否则会形成"1 1 1"}// 情况3：检查右边是否已经有两个连续的1else if (i + 2 <= n && s[i + 1] == 1 && s[i + 2] == 1){flag = false; // 不能安排，否则会形成"1 1 1"}// 如果当前座位可以安排新客人if (flag){s[i] = 1; // 将座位标记为已占用ans++; // 增加安排的客人数量}}cout << ans << endl; // 输出最大可安排的客人数量return 0;
}
【运行结果】
5
0 0 1 0 0
2
D - Operation Plan for Distribution Center
【题目来源】
AtCoder：D - Operation Plan for Distribution Center
【题目描述】
Takahashi is the manager of a delivery center. The delivery center has \(N\) packages to deliver, and each package has a "preferred delivery date" specified by its recipient. The preferred delivery date of the \(i\)-th package is day \(D_i\).
高桥是一个配送中心的管理员。配送中心有 \(N\) 个包裹需要投递，每个包裹都有一个由收件人指定的"期望投递日期"。第 \(i\) 个包裹的期望投递日期是第 \(D_i\) 天。
The delivery center can operate for exactly \(K\) consecutive days. Specifically, Takahashi chooses any integer \(s\) and sets the operation period to be the \(K\) days from day \(s\) to day \(s + K - 1\) (inclusive).
配送中心恰好运营 \(K\) 个连续的天数。具体来说，高桥选择一个整数 \(s\)，并将运营期间设置为从第 \(s\) 天到第 \(s + K - 1\) 天（含端点）的 \(K\) 天。
Takahashi must deliver all packages within this operation period. If the delivery date of the \(i\)-th package is \(x_i\), then \(x_i\) must be an integer satisfying \(s \leq x_i \leq s + K - 1\). There is no upper limit on the number of packages that can be delivered in a single day, and multiple packages can be delivered on the same day.
高桥必须在这个运营期间内投递所有包裹。如果第 \(i\) 个包裹的投递日期是 \(x_i\)，那么 \(x_i\) 必须满足 \(s \leq x_i \leq s + K - 1\) 的整数。每天可以投递的包裹数量没有上限，多个包裹可以在同一天投递。
If the \(i\)-th package is delivered on day \(x_i\), the dissatisfaction for that package is \(|D_i - x_i|\). If the package is delivered exactly on the preferred delivery date, the dissatisfaction is \(0\), but the further the delivery date is from the preferred date, the greater the dissatisfaction.
如果第 \(i\) 个包裹在第 \(x_i\) 天投递，该包裹的不满意度为 \(|D_i - x_i|\)。如果包裹恰好在期望投递日期投递，不满意度为 \(0\)，但投递日期与期望日期相差越远，不满意度就越大。
Takahashi wants to choose the starting day \(s\) of the operation period appropriately, and also decide the delivery date of each package within the operation period appropriately, in order to minimize the total dissatisfaction of all packages \(\displaystyle \sum_{i=1}^{N} |D_i - x_i|\). Find this minimum value.
高桥希望适当地选择运营期间的起始日 \(s\)，并在运营期间内适当地决定每个包裹的投递日期，以最小化所有包裹的总不满意度 \(\displaystyle \sum_{i=1}^{N} |D_i - x_i|\)。求此最小值。
【输入】
\(N\) \(K\)
\(D_1\) \(D_2\) \(\ldots\) \(D_N\)
- The first line contains \(N\), the number of packages, and \(K\), the number of days in the operation period, separated by a space.
- The second line contains the preferred delivery dates \(D_1, D_2, \ldots, D_N\) of each package, separated by spaces.
【输出】
Print the minimum value of the total dissatisfaction of all packages in one line.
【输入样例】
5 3
1 2 3 4 5
【输出样例】
2
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int n, k;
int d[N], sd[N]; // d存储数据，sd是前缀和数组signed main()
{cin >> n >> k; // 输入n个元素和区间长度k// 读取n个整数for (int i = 1; i <= n; i++){cin >> d[i];}// 对数组进行排序sort(d + 1, d + n + 1);// 计算前缀和：sd[i] = d[1] + d[2] + ... + d[i]for (int i = 1; i <= n; i++){sd[i] = sd[i - 1] + d[i];}int ans = 1e18; // 初始化答案为很大的数// 情况1：区间左端点与某个d[i]对齐for (int i = 1; i <= n; i++){int l = d[i]; // 区间左端点int r = l + k - 1; // 区间右端点// 使用二分查找找到在区间内的元素int left = lower_bound(d + 1, d + n + 1, l) - d; // 第一个 >= l 的位置int right = upper_bound(d + 1, d + n + 1, r) - d - 1; // 最后一个 <= r 的位置// 计算左侧代价：小于l的元素都要移动到l// 公式：数量 * l - 这些元素的和int left_cost = (left - 1) * l - sd[left - 1];// 计算右侧代价：大于r的元素都要移动到r// 公式：这些元素的和 - 数量 * rint right_cost = (sd[n] - sd[right]) - (n - right) * r;// 更新最小总代价ans = min(ans, left_cost + right_cost);}// 情况2：区间右端点与某个d[i]对齐for (int i = 1; i <= n; i++){int r = d[i]; // 区间右端点int l = r - k + 1; // 区间左端点// 使用二分查找找到在区间内的元素int left = lower_bound(d + 1, d + n + 1, l) - d; // 第一个 >= l 的位置int right = upper_bound(d + 1, d + n + 1, r) - d - 1; // 最后一个 <= r 的位置// 计算左侧代价int left_cost = (left - 1) * l - sd[left - 1];// 计算右侧代价int right_cost = (sd[n] - sd[right]) - (n - right) * r;// 更新最小总代价ans = min(ans, left_cost + right_cost);}cout << ans << endl; // 输出最小代价return 0;
}
【运行结果】
5 3
1 2 3 4 5
2
E - A Walk and Barricades
【题目来源】
AtCoder：E - A Walk and Barricades
【题目描述】
Takahashi is taking a walk on a one-dimensional number line. Initially, Takahashi is at coordinate \(0\).
高桥正在一条一维数轴上散步。初始时，高桥位于坐标 \(0\)。
Takahashi has \(N\) movement plans. Executing the \(i\)-th \((1 \leq i \leq N)\) plan adds \(D_i\) to his current coordinate. \(D_i\) is a non-zero integer; when positive, he moves in the positive direction, and when negative, he moves in the negative direction.
高桥有 \(N\) 个移动计划。执行第 \(i\) 个（\(1 \leq i \leq N\)）计划会将他的当前坐标增加 \(D_i\)。\(D_i\) 是一个非零整数；当为正数时，他向正方向移动；当为负数时，他向负方向移动。
There are \(M\) barricades placed on the number line. The \(j\)-th \((1 \leq j \leq M)\) barricade is at coordinate \(X_j\). When executing a plan moves Takahashi from his current coordinate \(s\) to coordinate \(s + D_i\), if there exists at least one barricade between \(s\) and \(s + D_i\) (inclusive of both endpoints), that is, if there exists an \(X_j\) satisfying \(\min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i)\), then a collision occurs and the plan cannot be executed.
数轴上放置了 \(M\) 个路障。第 \(j\) 个（\(1 \leq j \leq M\)）路障位于坐标 \(X_j\)。当执行一个计划将高桥从当前坐标 \(s\) 移动到坐标 \(s + D_i\) 时，如果在 \(s\) 和 \(s + D_i\) 之间（包含两端点）存在至少一个路障，也就是说，如果存在一个 \(X_j\) 满足 \(\min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i)\)，则会发生碰撞，该计划无法执行。
Takahashi considers the plans in order from the \(1\)-st to the \(N\)-th. For each plan, if a collision would occur, he must skip that plan. If no collision would occur, he may freely choose to either execute or skip the plan.
高桥按顺序考虑第 \(1\) 到第 \(N\) 个计划。对于每个计划，如果会发生碰撞，他必须跳过该计划。如果不会发生碰撞，他可以自由选择执行或跳过该计划。
Find the maximum possible coordinate of Takahashi after all plans have been considered.
求在考虑完所有计划后，高桥可能达到的最大坐标。
【输入】
\(N\) \(M\)
\(D_1\) \(D_2\) \(\ldots\) \(D_N\)
\(X_1\) \(X_2\) \(\ldots\) \(X_M\)
- The first line contains the number of plans \(N\) and the number of barricades \(M\), separated by a space.
- The second line contains the coordinate changes \(D_1, D_2, \ldots, D_N\) for each plan, separated by spaces.
- The third line contains the coordinates \(X_1, X_2, \ldots, X_M\) of each barricade, separated by spaces. However, if \(M = 0\), the third line is not given.
【输出】
Print in one line the maximum possible final coordinate of Takahashi when plans are chosen optimally.
【输入样例】
4 2
3 -2 4 -1
2 5
【输出样例】
0
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50005, M = 200005;
int n, m;
int d[N], x[M];signed main()
{cin >> n >> m; // 输入n和m// 读取n个整数到数组dfor (int i = 1; i <= n; i++){cin >> d[i];}// 读取m个整数到数组xfor (int i = 1; i <= m; i++){cin >> x[i];}// 初始化bitset B，用于标记x[i]的存在// 偏移N=50005，使得负数索引变为正数bitset<M> B;// 将所有x[i]在[-50000, 50000]范围内的值标记在B中for (int i = 1; i <= m; i++){if (-50000 <= x[i] && x[i] <= 50000){B.set(x[i] + N); // 设置对应位置为1}}// dp bitset，dp[i]表示是否能到达位置i// 初始位置设为0，偏移Nbitset<M> dp;dp.set(N); // dp[N]表示位置0// 动态规划：处理每个d[i]for (int i = 1; i <= n; i++){bitset<M> blk; // 阻塞位置集合if (d[i] > 0) // 如果d[i]为正数，向右移动{// 计算阻塞位置：对于每个j∈[0,d[i]]，B右移j位的位置都是阻塞的for (int j = 0; j <= d[i]; j++){blk |= B >> j; // 将B右移j位后的阻塞位置合并}// 状态转移：从可到达且不阻塞的位置向右移动d[i]位dp |= ((dp & ~blk) << d[i]);}else // 如果d[i]为负数，向左移动{d[i] *= -1; // 取绝对值// 计算阻塞位置：对于每个j∈[0,d[i]]，B左移j位的位置都是阻塞的for (int j = 0; j <= d[i]; j++){blk |= B << j; // 将B左移j位后的阻塞位置合并}// 状态转移：从可到达且不阻塞的位置向左移动d[i]位dp |= ((dp & ~blk) >> d[i]);}}// 寻找最大可达位置int ans = 0;for (int i = -50000; i <= 50000; i++){if (dp[i + N]) // 如果位置i可达{ans = i; // 更新答案}}cout << ans << endl; // 输出最大可达位置return 0;
}
【运行结果】
4 2
3 -2 4 -1
2 5
0