专栏文章

题解：P1249 最大乘积

wwenqinghua1001
P1249题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miorkg1g
此快照首次捕获于
2025/12/02 23:59
3 个月前
此快照最后确认于
2025/12/02 23:59
3 个月前
查看原文

思路

大家看到这题的时候，都想 DFS，结果超时，3≤n≤100003 \le n \le 10000。不能暴力，那也只有贪心了。
首先，不可能将 nn 分解出 11，因为 11 和任何数乘，结果没变。这样会浪费 nn 的资源，不是最优。
然后特判一下，当 n≤4n \le 4 时，自己本身就是最优解。
我们思考一下，如果有两个数的和是 xx，那么这两个数的积最大是多少？很明显，这两个数的差尽量小，也就是尽量连在一起。设 x=10x=10，那么这两个数最优是 55 和 55，它们的积是 5×5=255 \times 5 = 25。
三个数呢？同理，越连续越好。设 n=∑i=1kain=\sum_{i=1}^{k} a_i，使 ∏j=1kaj\prod_{j=1}^{k} a_j 最大，则尽量满足 ∣a1−a2∣=0,∣a2−a3∣=0,⋯ ,∣ak−1−ak∣=0\lvert a_1-a_2 \rvert=0,\lvert a_2-a_3 \rvert=0, \cdots ,\lvert a_{k-1}-a_k \rvert=0，也就是我们小学学的“和同近积大”。
知道这个后，对 nn 进行分解，从 22 开始。
CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int main(){
	int n,sum=0,num=2,p=0;
	cin>>n;
	if(n<=4){
		cout<<n<<endl<<n;
		return 0;
	}
	// 特判 
	while(sum<n){
		if(n-sum<num)
			break;
		a[++p]=num;
		sum=sum+num;
		num++;
		// 分解 
	}
	int s=n-sum;
代码中，ss 表示 nn 分剩下的数，不能浪费，继续分给 aa 数组。按 aa 数组中的值从大到小分，这是最优情况。在上面的代码中按 pp 从大到小分。
CPP
	int tmp=p;
	while(s>0){
		// 将剩下的 s 分配到 a
		a[tmp--]++;
		s--;
		// s 分出一个 1 给 a[tmp] 
		if(tmp==0) tmp=p;
		// 循坏，直到分完 
	}
Subtask #1 没过的看这里，一定要 if(tmp==0) tmp=p;，不然会浪费资源。对于 88 就会浪费。
最后，将 aa 数组中所有分解的数乘起来，就是最优答案。
CPP
	int ans=1;
	for(int i=1;i<=p;i++){
		cout<<a[i]<<" ";
		ans=ans*a[i];
	}
	cout<<endl<<ans;
	// 乘积 
	return 0;
}
代码打完了，提交上去，20 pts，回来看了看题目，3≤n≤100003 \le n \le 10000，那乘积该多大！高精度解决。

代码

AC 记录
CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int b[100001];
string chengfa(string s,string t){
	memset(b,0,sizeof(b));
	reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
	int i,j;
    for(i=0;i<s.size();i++)
        for(j=0;j<t.size();j++)
            b[i+j]+=(s[i]-'0')*(t[j]-'0');
    for(int i=0;i<s.size()+t.size();i++){
        b[i+1]+=b[i]/10;
        b[i]=b[i]%10;
    }
    i=s.size()+t.size();
    while(b[i]==0&&i>0) i--;
    string ans="";
    for(int jj=i;jj>=0;jj--){
    	char x=b[jj]+'0';
    	ans=ans+x;
    }
    return ans;
}
string c(int x){
	stringstream ss;
	ss<<x;
	string d;
	ss>>d;
	return d;
}
int main(){
	int n,sum=0,num=2,p=0;
	cin>>n;
	if(n<=4){
		cout<<n<<endl<<n;
		return 0;
	}
	// 特判 
	while(sum<n){
		if(n-sum<num)
			break;
		a[++p]=num;
		sum=sum+num;
		num++;
		// 分解 
	}
	int s=n-sum;
	int tmp=p;
	while(s>0){
		// 将剩下的 s 分配到 a
		a[tmp--]++;
		s--;
		// s 分出一个 1 给 a[tmp] 
		if(tmp==0) tmp=p;
		// 循坏，直到分完 
	}
	string ans="1";
	for(int i=1;i<=p;i++){
		cout<<a[i]<<" ";
		ans=chengfa(ans,c(a[i]));
	}
	cout<<endl<<ans;
	// 乘积 
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...