UVa 668 - Parliament

链接

传送门

大意

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

思路

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

代码

#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;
}