2024.3.8力扣每日一题——找出美丽数组的最小和

2024.3.8

• • • 题目来源
    • 我的题解
    • • 方法一 数学

题目来源

力扣每日一题；题序：2834

我的题解

方法一 数学

经过分析，在target之前，取小于等于target/2的正整数才能使得和最小，并且满足条件3。

时间复杂度：O(n)
空间复杂度：O(n)

public int minimumPossibleSum(int n, int target) {
    if(n==1)
        return 1;
    long res=0;
    int mod=1000000007;
    for(int i=1;i<=target/2&&i<=n;i++){
        res+=i;
    }
    for(int i=target/2;i<n;i++){
        res+=target++;
    }
    return (int)(res%mod);
}

//优化版本
public int minimumPossibleSum(int n, int target) {
    if(n==1)
        return 1;
    long res=0;
    int mod=1000000007;
    //若target左边取的就已经够n格数了
    if(target/2>=n){
        res+=n*(1L+n)/2;
    }else{
        long t=target/2;
        //target左边可以取的所有正整数的和
        res+=t*(1L+t)/2;
        //左边取了之后，还需要取多少个数
        t=n-t;
        //target本身及其右边可以取的所有正整数的和
        res+=t*(target+target+t-1)/2;
    }
    return (int)(res%mod);
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈