题解：P16353 「Diligent-OI R3 A」说好不哭

ZhangChuan1350 · 2026-04-26 21:14:59 · 题解

题目要求是否存在一个长度为 n 的整数序列满足最大非空子段和为 x，最小非空子段和为 y，并给出了序列、子段的定义。

分几种情况讨论：

• 若 n=1，则序列只有一个数字。此时序列存在，当且仅当 x=y。
  这很好理解，如果一个序列只有 1 个数字，那最大非空子段和一定和最小非空子段和是相等的，否则就不止 1 个数字了。
• 若 n\ge1，再对 x,y 是 同号 / 异号 分情况：
  • 若 x>0 且 y<0，则一定存在序列。因为可以构造一个序列至少包含两个一正一负的数字。
  • 若 x\ge0 且 y\ge0，则当且仅当 x\ge n\cdot y 时，序列存在，否则序列不存在。因为此时序列必须包含 y（否则最小就不是 y），再至少包含一个长度为 (n-1) 的序列 a，满足 a_i\ge y 且 \sum a_i+y\le x（a_i 表示序列 a 的第 i 个数，\sum a_i 表示序列 a 全部数字之和）。
  • 若 x<0 且 y<0，则当且仅当 y\leqslant n\cdot x 时，序列存在，否则序列不存在。
    此证明与 Case 2 相似，在这里不再详细展开。

代码如下： :::success[AC Code]

#include <cstdio>
int T;
long long n,x,y;
int main()
{
    scanf("%lld",&T);
    while (T--){
        scanf("%lld%lld%lld",&n,&x,&y);
        if (n==1){
            if (x==y) puts("YES");
            else puts("NO");
            continue;
        }
        if (x>0&&y<0) puts("YES");
        else if (x>=0&&y>=0){
            if (x>=n*y) puts("YES");
            else puts("NO");
        } else{
            if (y<=n*x) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

:::