把所有的谎言献给你β

Problem Description
In the world line 1.048596
梓川咲太的面前坐着野兔先辈,作为约定,只好乖乖的打开笔记本开始学习了
“加法符号写歪了,变成了乘法符号,在算式的第三行那个地方。”樱岛麻衣突然开口
心领神会的梓川咲太立刻发现自己正在写的题目的错误,乖乖的改正了以后却心不在焉
毕竟,梓川咲太的眼神却很不老实,毕竟,眼前坐着野兔先辈
“咲太,假设我给你一个正整数n,你是不是可以把它用许多不同的整数(包括它自己)去减然后把n变成0?
樱岛麻衣开始穿上披风
这是生气的前兆,即将没了眼福的梓川咲太只能不停的点了点头
“那行,一个正整数n的做减法的操作过程也有很多种,比如说6就能变成6-6=0,6-1-5=0和6-2-4=0,对吧。但是不能变成6-3-3=0,因为3重复了。
樱岛麻衣用漂亮的字体在笔记本上书写
“当然写成6=6,6=1+5,6=2+4更好,相当于这些正整数构成一个序列{a1,a2,…,an}满足(Σai = N),(n >= 1),且这些正整数互不相同。
“那么刚刚的例子就是{6},{1,5},{2,4}这样。
“有没有想过把这些序列的数字乘起来呢?就像加法符号变成乘法一样,结果就是6,1×5,2×4这样…
”就把这样操作后的结果称为M吧,对于一个正整数n,不同的拆分能得出不同的M,但M也是有最大值和最小值的。比如说刚刚那个例子,M的最大值是8,最小值是5。
此时的梓川咲太还不知道即将到来的地狱
“你刚刚的眼神这么不老实,大概看了几十下了吧。我就大发慈悲的写一些数字,你给我马上写出每个数字经过操作以后得出来的M的最小值和最大值。
“不把这些写完,今晚不让你睡哦。
麻衣打开的笔记本上密密麻麻的排列着许多数字,野兔先辈的代价实在是太大了,不过约定就是约定…

Input
第一行输入一个正整数T(T<=200),表示样例组数,接下去T行每行表示一组样例。
每组样例,输入一个正整数N(1<=N<=200)

Output
输出总共T行。
每行输出两个整数,表示每个数字经过操作以后得出的数字M的最小值和最大值,用一个空格隔开。

Sample Input
2
3
6

Sample Output
2 3
5 8

题解:分析几个数之后,我的直觉告诉我,最小值就是n-1,而最大值应该是把n拆成尽可能多的数,而且这些数尽量最接近。那么我们分析一下6,6可以拆成1+2+3,也可以分为2+4,很显然后者是最优解,那么是不是说我们的结论错了呢(我一开始就是死在这一步)。其实不是的,观察一下就会发现,只要拆出来的数字里包含1,那么我们就可以把1放到最大的那个数字里,这样操作之后得到的乘积总会比原来大。于是我们想到可以从2开始拆分数字。

  • 例如:
  • 8拆成两个,因为2+3<=8,2+3+4>8
  • 17拆成4个,因为2+3+4+5<=17,2+3+4+5+6>17

相应的,根据等差数列求和公式,我们可以知道给出任意数x,它可以最多拆成n个数;

那么如何让这n个数尽可能接近呢。观察我们拆分的数可知,前n-1个数是严格递增的,而最后一个数可能比倒数第二个大得多,于是我们可以每次将第n个数拿走1加到前面的数上,加的顺序当然是从n-1到1,因为不能重复。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ling long
#define INF 0×3f3f3f3f  //0×7ffffff
#define EPS 1e-6
#define maxn 20000+10
#define PI acos(-1.0)
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t,x;
    ll res;
    int a[maxn];
    while(cin>>t)
    {
        while(t--)
        {
            memset(a,0,sizeof(a));
            res=1;
            cin>>x;
            if(x==1||x==2) {cout<<x<<" "<<x<<endl;continue;}
            if(x==3||x==4) {cout<<x-1<<" "<<x<<endl;continue;}
            for(int i=1;i<=20;i++)
            {
                if((3+i)*i/2>x) {n=i-1;break;}  //表示拆成n个数相加;此处有坑,应该是从2开始
            }
            for(int i=2;i<=n;i++)
                a[i-1]=i;
            a[n]=x-(n-1)*(n+2)/2;
            int pop=n-1;
            if(a[n]-a[n-1]>2) //为什么此循环只用循环一次留给读者思考
            {
                while(a[n]-a[n-1]>1&&pop>0)  //此处为坑,不写pop>0的话数组下标会越界
                {
                    a[pop--]++;
                    a[n]--;
                }
            }
            for(int i=1;i<=n;i++)
                res*=a[i];
            cout<<x-1<<" "<<res<<endl;
        }
    }
    return 0;
}

 

发表评论,支持MarkDown语法