题解P1887 乘积最大3

Posted by n0000000000o's Blog on April 18, 2018

题目 P1887

只要仔细分析,我们就可以发现这是一道很简单的数学题(最开始以为是模拟,,后来看标签发现是数论)

首先从最简单的问题开始分析,假设m为2,就是分为两组使之和最大,那么有一个结论

已知x+y=k(k为常数),S=x*y,当x=y时,有S的最大值。(证明)

由此可以类推,

当一个数n被分为m份时,当每份数量相等,这m个数的乘积最大

因而我们只需要使这m个数都相等就行了,所以有了

q=n/m

但这时我们遇到了一个问题,题目要求每个数都为整数

所以每个数要

尽量的接近q

又因为在C语言中,整形n/m结果为整数向下取整,所以结果只有两种可能 这两个数只有两种

  • n/m
  • n/m +1

这就是大概思路,在此附上代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int w=n/m;
    int q=0;
    //while(w*m+q<n) q++; //q就是需要+1的数量
    //最开始使用的循环模拟 后来发现不用 
    // 因为 w*m+q=n  所以q=n-w*m  
    for(int i=1;i<=m;i++)
        if(i<m-(n-w*m)+1) 
            cout<<w<<" ";
        //这里的n-w*m就是q,利用q输出两种结果
        else    cout<<w+1<<" ";
    return 0;       
}