洛谷 LGR-171 赛后总结中，有哪些策略可以借鉴？
摘要：洛谷 LGR-171 赛后总结 比赛链接：https:www.luogu.com.cncontest146495 建议先看原题再看文章。 A - Water（P10056） 有 (n) 个杯子，每个杯子的容积是 (a)，且初
洛谷 LGR-171 赛后总结
比赛链接：https://www.luogu.com.cn/contest/146495
建议先看原题再看文章。
A - Water（P10056）
有 \(n\) 个杯子，每个杯子的容积是 \(a\)，且初始装有 \(b\) 体积水。
你可以进行任意次操作，每次操作选择任意两个杯子，将其中一个杯子内的水全部倒入另一个杯子中，但是过程中杯子里的水不能溢出（即不能超过其容积），如果不满足则无法进行该操作。请通过合法的操作，最大化装有最多水的杯子里水的体积。
Module 1 总结
赛时是一眼秒的。
显然把水全倒在一个杯子里，得到的答案最大，也就是 \(b \times n\)。但是可能会溢出，容量为 \(x\) 的情况下，最多能装 \(\Big\lfloor \dfrac{x}{b} \Big\rfloor\) 个初始装有 \(b\) 体积的水杯的容量。所以答案是 \(\min\Big(n \times b,\ b \times \Big\lfloor \dfrac{x}{b} \Big\rfloor\Big)\)。
记得开 long long！
Module 2 代码
Code
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
const int kMaxN = 5050, kMaxM = 5e4 + 50, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll a, b, n;
cin >> a >> b >> n;
cout << min(n * b, b * (a / b)) << '\n';
return 0;
}
B - Line（P10057）
在一个二维平面内，给定两条分别与 \(x\) 轴和 \(y\) 轴平行的线段 \(AB\) 和 \(CD\)。你可以选择一条线段，将其沿着平行于坐标轴（上下左右）的任意一个方向平移任意单位长度，称为一次操作。问至少进行几次操作可以使两条线段相交？
Module 1 总结
赛时思考了一会，还错了 \(3\) 次。
首先，题目中说 \(x_A<x_B\)，\(x_C=x_D\)，\(y_A=y_B\)，\(y_C<y_D\)。所以我们发现，第一条线段是竖的，第二条是横的。所以我们先判断第一段和第二段的 \(x\) 轴是否重合（\(x_A \le x_C \le x_B\) 或 \(x_A \le x_D \le x_B\)），如果不是，答案 \(+1\)。再判断 \(y\) 轴是否重合（\(y_C \le y_A \le y_D\) 或 \(y_C \le y_B \le y_D\)），如果不是，答案 \(+1\)。