题解：P16353 「Diligent-OI R3 A」说好不哭
0x00AC3375
·
·
题解
1. 题意
输入三个数 n,x,y，判断是否存在一个长度为 n 的整数序列满足最大非空子段和为 x，最小非空子段和为 y。
2. 分析
比较入门的构造类题目。
按 n 的大小以及 x, y 的符号进行分类。
（1）当 n = 1 时
序列只有一个元素 a_1。此时最大非空子段和与最小非空子段和都等于 a_1。
此时充要条件直接就是 x=y。
（2）当 n \ge 2 时
::::info{open}
本部分分析少量借助 Qwen 3.6 完成。
::::
要判断是否存在这样的子段，根据 x, y 的符号分为三种情况。
此时令序列为 $\{x, y, 0, 0, \dots, 0\}$。如此一来由于 $y \le 0 \le x$，任意子段和必然落在 $[y, x]$ 区间内。包含 $x$ 的子段最大值为 $x$，包含 $y$ 的子段最小值为 $y$。中间的 $0$ 不会改变最值。
$x \ge y\ge 0$：
此时所有子段和均为正，说明序列中**不能有非正数**（否则会出现 $\le 0$ 的子段和，与最小值为正矛盾）。对于全正序列：
- 最大子段和一定是**整个序列的总和**（加正数只会变大）。
- 最小子段和一定是**最小的单个元素**（任意更长子段和都大于其中任一元素）。
- 因此必须满足：总和为 $x$，且每个元素 $\ge y$。即 $x \ge n \cdot y$。
此时的充要条件是 $x\ge ny$。构造方法是 $a_1 = x - (n-1)y$，其余 $a_i = y$。由条件知 $a_1 \ge y$，所有元素为正，满足题意。
$x < 0$（此时必有 $y \le x < 0$，全负情况）：
此时所有子段和均为负，说明序列中**不能有非负数**。
对于全负序列，最小子段和一定是**整个序列的总和**（加负数只会变小），最大子段和一定是**最大的单个元素**（即绝对值最小的负数）。
因此必须满足：总和为 $y$，且每个元素 $\le x$。即 $y \le n \cdot x$。
此时的充要条件是 $y\le nx$。构造方法是 $a_1 = y - (n-1)x$，其余 $a_i = x$。由条件知 $a_1 \le x$，所有元素为负，满足题意。
汇总以上结果，我们直接上伪代码。
::::info[伪代码]{open}
对每组数据 $(n, x, y)$：
1. 若 `n == 1`：
- 判断是不是 `x == y`
2. 若 `n >= 2`：
- 若 `x >= 0 and y <= 0`
- 直接输出 `YES`
- 若 `x >= 0 and y > 0`
- 判断 `x >= n * y`
- 若 `x < 0`
- 判断 `y <= n * x`
::::
最后单组数据直接就是 $O(1)$ 的常数复杂度了。
## 3. 代码
::::success[C#]
```csharp
using System;
class P16353
{
static void Solve()
{
string line = Console.ReadLine();
int T = Convert.ToInt32(line);
while (T-- > 0)
{
string[] inputs = Console.ReadLine().Split();
long n = long.Parse(inputs[0]);
long x = long.Parse(inputs[1]);
long y = long.Parse(inputs[2]);
bool ok = false;
if (n == 1)
{
ok = (x == y);
}
else
{
if (x >= 0 && y <= 0)
{
ok = true;
}
else if (x >= 0 && y > 0)
{
ok = (x >= n * y);
}
else
{
ok = (y <= n * x);
}
}
Console.WriteLine(ok ? "YES" : "NO");
}
}
static void Main()
{
Solve();
}
}
```
::::
::::success[C++]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int T;
if (!(cin >> T)) return;
while (T--)
{
ll n, x, y;
cin >> n >> x >> y;
bool ok = false;
if (n == 1)
{
ok = (x == y);
}
else
{
if (x >= 0 && y <= 0)
{
ok = true;
}
else if (x >= 0 && y > 0)
{
ok = (x >= n * y);
}
else
{
ok = (y <= n * x);
}
}
cout << (ok ? "YES\n" : "NO\n");
}
}
int main()
{
solve();
return 0;
}
```
::::