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

Link: https://www.luogu.com.cn/problem/P16353

题目描述

小 C 想知道，是否存在一个长度为n nn的整数序列满足最大非空子段和为x xx，最小非空子段和为y yy。

若存在，输出YES，否则输出NO。

请注意，若序列b bb可以通过将序列a aa分别在前面和后面删除若干个元素（可以为 0 个）得到，则定义b bb是a aa的子段。

输入格式

本题有多组测试数据。

输入的第一行包含一个整数T TT，表示测试数据的组数。

接下来包含T TT组数据，对于每组数据，输入一行包含三个整数n , x , y n,x,yn,x,y。

输出格式

对于每组数据输出一行YES或NO，表示是否存在满足条件的序列。

输入输出样例 #1

输入 #1

7 5 5 0 2 3 1 2 5 3 1 5 -1 3 -1 -2 3 -1 -3 4 3 -4

输出 #1

YES YES NO NO NO YES YES

说明/提示

【样例解释】

第一组数据可构造出：{ 1 , 2 , 1 , 1 , 0 } \{1,2,1,1,0\}{1,2,1,1,0}。

第二组数据可构造出：{ 2 , 1 } \{2,1\}{2,1}。

可以证明，第三、四、五组数据无法构造出满足题意的序列。

第六组数据可构造出：{ − 1 , − 1 , − 1 } \{-1,-1,-1\}{−1,−1,−1}。

第七组数据可构造出：{ 1 , 2 , − 2 , − 2 } \{1,2,-2,-2\}{1,2,−2,−2}。

【数据范围】

• 特殊性质：x , y x,yx,y均为非负整数。

对于所有数据，保证1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤105，1 ≤ n ≤ 10 9 1\le n\le 10^91≤n≤109，− 10 9 ≤ y ≤ x ≤ 10 9 -10^{9}\le y \le x\le 10^{9}−109≤y≤x≤109。

Solution

1. 题意

输入三个数n , x , y n,x,yn,x,y，判断是否存在一个长度为n nn的整数序列满足最大非空子段和为x xx，最小非空子段和为y yy。

2. 分析

比较入门的构造类题目。

按n nn的大小以及x , y x, yx,y的符号进行分类。

（1）当n = 1 n = 1n=1时

序列只有一个元素a 1 a_1a1​。此时最大非空子段和与最小非空子段和都等于a 1 a_1a1​。

此时充要条件直接就是x = y x=yx=y。

（2）当n ≥ 2 n \ge 2n≥2时

要判断是否存在这样的子段，根据x , y x, yx,y的符号分为三种情况。

x ≥ 0 x \ge 0x≥0且y ≤ 0 y \le 0y≤0：

此时令序列为{ x , y , 0 , 0 , … , 0 } \{x, y, 0, 0, \dots, 0\}{x,y,0,0,…,0}。如此一来由于y ≤ 0 ≤ x y \le 0 \le xy≤0≤x，任意子段和必然落在[ y , x ] [y, x][y,x]区间内。包含x xx的子段最大值为x xx，包含y yy的子段最小值为y yy。中间的0 00不会改变最值。

x ≥ y ≥ 0 x \ge y\ge 0x≥y≥0：

此时所有子段和均为正，说明序列中不能有非正数（否则会出现≤ 0 \le 0≤0的子段和，与最小值为正矛盾）。对于全正序列：

• 最大子段和一定是整个序列的总和（加正数只会变大）。
• 最小子段和一定是最小的单个元素（任意更长子段和都大于其中任一元素）。
• 因此必须满足：总和为x xx，且每个元素≥ y \ge y≥y。即x ≥ n ⋅ y x \ge n \cdot yx≥n⋅y。

此时的充要条件是x ≥ n y x\ge nyx≥ny。构造方法是a 1 = x − ( n − 1 ) y a_1 = x - (n-1)ya1​=x−(n−1)y，其余a i = y a_i = yai​=y。由条件知a 1 ≥ y a_1 \ge ya1​≥y，所有元素为正，满足题意。

x < 0 x < 0x<0（此时必有y ≤ x < 0 y \le x < 0y≤x<0，全负情况）：

此时所有子段和均为负，说明序列中不能有非负数。
对于全负序列，最小子段和一定是整个序列的总和（加负数只会变小），最大子段和一定是最大的单个元素（即绝对值最小的负数）。

因此必须满足：总和为y yy，且每个元素≤ x \le x≤x。即y ≤ n ⋅ x y \le n \cdot xy≤n⋅x。

此时的充要条件是y ≤ n x y\le nxy≤nx。构造方法是a 1 = y − ( n − 1 ) x a_1 = y - (n-1)xa1​=y−(n−1)x，其余a i = x a_i = xai​=x。由条件知a 1 ≤ x a_1 \le xa1​≤x，所有元素为负，满足题意。

汇总以上结果，我们直接上伪代码。

伪代码

对每组数据( n , x , y ) (n, x, y)(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 ) O(1)O(1)的常数复杂度了。

3. 代码

C#

usingSystem;classP16353{staticvoidSolve(){stringline=Console.ReadLine();intT=Convert.ToInt32(line);while(T-->0){string[]inputs=Console.ReadLine().Split();longn=long.Parse(inputs[0]);longx=long.Parse(inputs[1]);longy=long.Parse(inputs[2]);boolok=false;if(n==1){ok=(x==y);}else{if(x>=0&&y<=0){ok=true;}elseif(x>=0&&y>0){ok=(x>=n*y);}else{ok=(y<=n*x);}}Console.WriteLine(ok?"YES":"NO");}}staticvoidMain(){Solve();}}

C++

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;voidsolve(){intT;if(!(cin>>T))return;while(T--){ll n,x,y;cin>>n>>x>>y;boolok=false;if(n==1){ok=(x==y);}else{if(x>=0&&y<=0){ok=true;}elseif(x>=0&&y>0){ok=(x>=n*y);}else{ok=(y<=n*x);}}cout<<(ok?"YES\n":"NO\n");}}intmain(){solve();return0;}