UVa 668 - Parliament

链接

传送门

大意

给出一个正整数$n(5 \leq n \leq 1000)$, 输出将它分解为尽可能多的大于2的不同的正整数之和,输出分解方案,输出时最小值要尽量大。

思路

预处理出从2开始的连续和,对于输入的数字,先算出从2开始最长的可选择选择的序列,然后将剩余的值从后向前分配给被选中的连续序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int sum[maxn];
int main() {
sum[2] = 2;
for (int i = 3; i < maxn; ++i) {
sum[i] = sum[i - 1] + i;
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int p = int(upper_bound(sum, sum + maxn, n) - sum) - 1;
n -= sum[p];
int num = p - 2 + 1, pl = n / num;
n = p - (n % num);
for (int i = 2; i <= p; ++i) {
printf("%d%c", i <= n ? i + pl : i + pl + 1, i == p ? '\n' : ' ');
}
if (t) {
puts("");
}
}
return 0;
}

支付宝扫码领红包