题目链接
题意:
让你用n个正整数去构成和为S的数组(n，S将给出)，问是否存在一个k(1 <= k <= S)使得这个数组中的任意子数组的和不为k，如果存在输出yes，并且输出这个数组和k，否则输出no。
思路:
我们先贪心一下，直接把数组的前n-1个数，赋值成1，然后最后一个数赋值成s-(n-1)。
1.我们先看这个数组的前n-1个数的子数组的和的范围。
很容易知道，范围为:1到n-1。
2.再看包含最后一个数的子数组的范围是多少。
范围为s-(n-1)到s。
3.我们再判断第一步的最大值(也就是n-1)是否大于或等于第二步的最小值-1。
实际上，就是最大化数组中的和的范围，然后再判断其中是否存在和不连续的情况
【codeforces|Codeforces Round #643 (Div. 2) D. Game With Array (思维，贪心)】AC代码:
#include
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const unsigned long long mod = 998244353;
const double II = 3.1415926535;
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
typedef pair piil;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,s;
cin >> n >> s;
int Min = s-n+1,Max = n-1;
if(Max >= Min-1) cout << "NO" << endl;
else
{
cout << "YES" << endl;
for(int i = 1;
i <= n-1;
i++) cout << 1 << " ";
cout << Min << endl;
cout << Max+1 << endl;
}
}
推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element