Question
定义一个三元组 \((x,y,z)\) 是 “v - 三元组” 当且仅当该三元组满足以下条件:
- \(x = z\)
- \(x > y\)
现在需要你构造一个 \(n\) 个正整数组成的数组,所有元素之和恰好等于 \(S\), 且恰好有 \(k\) 个长度威 \(3\) 的连续子数组是 "v - 三元组"
Solution
贪心的想, 如果用最少的元素和先构造出 \(k\) 个 "v - 三元组",剩下的元素随意放在后面就好了
那么简单得,最少的方案就是 2 1 2 1 2 1 ......
如果后面没有位置了,即 \(n = 2k + 1\)
那么就先集体增加 \(2\),然后增加 \(1\) 的位置
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
LL n, S, k; cin >> n >> S >> k;
vector<LL> a(n + 1);
int m = 2 * k + 1;
if (k == 0) {
S -= n;
if (S < 0) {
cout << -1 << endl;
return;
}
for (int i = 1; i <= n; i++)
a[i] = 1;
a[1] += S;
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
return;
}
if (n < m) {
cout << -1 << endl;
return;
}
else if (n == m) {
LL sum_1 = k * 1, sum_2 = (k + 1) * 2;
S -= sum_1 + sum_2;
if (S < 0) {
cout << -1 << endl;
return;
}
LL x = S / (k + 1); S -= x * (k + 1);
for (int i = 1; i <= m; i += 2) {
a[i] = 2 + x;
}
for (int i = 2; i <= m; i += 2) {
if (S > 0) {
if (x == 0) {
cout << -1 << endl;
return;
}
a[i] = 2; S -= 1;
}
else a[i] = 1;
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
else if (n > m) {
LL sum_1 = k * 1, sum_2 = (k + 1) * 2;
S -= sum_1 + sum_2;
for (int i = 1; i <= m; i++) {
if (i & 1) a[i] = 2;
else a[i] = 1;
}
for (int i = m + 1; i <= n; i++) {
a[i] = 1; S -= 1;
}
if (S < 0) {
cout << -1 << endl;
return;
}
a[m + 1] += S;
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) solve();
return 0;
}
标签:题解,sum,三元组,2024,牛客,集训营,LL
From: https://www.cnblogs.com/martian148/p/18032328