考点
题解
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include <bits/stdc++.h>
using namespace std;
const int LEN = 25050;
class BigInt
{
public:
int len_;
int arr_[LEN];
int &operator[](int idx)
{
return arr_[idx];
}
BigInt(int x = 0)
{
memset(arr_, 0, sizeof(arr_));
for (len_ = 1; x; ++len_)
{
arr_[len_] = x % 10;
x /= 10;
}
--len_;
}
void flatten(int len)
{
len_ = len;
for (int i = 1; i <= len_; ++i)
{
if (arr_[i] >= 10)
{
arr_[i + 1] += arr_[i] / 10;
arr_[i] %= 10;
}
}
while (!arr_[len_])
--len_;
}
void print()
{
for (int i = max(1, len_); i >= 1; --i)
{
cout << arr_[i];
}
}
};
BigInt operator*(BigInt a, int b)
{
BigInt c;
int len = a.len_;
for (int i = 1; i <= len; ++i)
{
c[i] += a[i] * b;
}
c.flatten(len + 11);
return c;
}
int main()
{
int arr[10001], n, idx = 0, sum = 0;
memset(arr, 0, sizeof(arr));
cin >> n;
for (int i = 2; sum < n; ++i)
{
sum += i;
arr[idx++] = i;
}
int diff = sum - n;
if ((diff == 1))
{
arr[0] = 1;
++arr[idx - 1];
}
else
{
for (int i = 0; i < idx; ++i)
{
if (arr[i] == diff)
{
arr[i] = 1;
break;
}
}
}
BigInt a(1);
for (int i = 0; i < idx; ++i)
{
a = a * arr[i];
}
for (int i = 0; i < idx; ++i)
{
if (arr[i] == 1)
continue;
cout << arr[i] << " ";
}
cout << endl;
a.print();
return 0;
}
|
思路
题目要求将整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大
若单单是乘积最大，很容易想到贪心策略——把n尽可能地拆散均匀即可；但题目要求互不相同
以n=11为例
尝试从2开始枚举自然数，一直到这些自然数的和大于等于n；枚举结束时，集合应该是{2,
3, 4, 5}，集合的和为14
此刻，集合的和相较于n多了3；那么问题就转换为怎么让集合内的数减3，使它们的乘积最大
显然唯一的办法就是直接从集合中移除数字3，因为要求互不相同；倘若集合内的任何一个数减1，都会有碰撞
再以n=13为例
集合的和相较于n多了1，但集合内并没有数字1；将数字2移除（必定存在），相当于减2，再将最大的数字加1即可保持平衡
故而总体步骤如下：
- 从数字2开始枚举自然数集合，直到集合的和大于等于n
- 和与n的差值等于1，删除数字2（这里把数字2设置为数字1即可，因为目标只是算乘积）并将最大的数字加1
- 和与n的差值大于1，删除差值相同的数字即可
- 遍历集合，用高精乘低精的模板计算乘法结果