C語言程式設計100例之（45）：最大乘積

例45  最大乘積

問題描述

給定一個整數 n，找到三個整數 x,y,z，要求滿足 x+y+z=n且 x,y,z都能整除 n，且使得乘積xyz 的值最大，求 xyz的最大值，

輸入格式

第一行為一個整數 T  (1≤T≤10⁶)，表示資料組數，接下去 T 行每行一個整數 n (1≤n≤10⁶)，

輸出格式

如果存在滿足條件的 x,y,z的值，輸出其中 xyz的最大值，如果不存在滿足條件的值，則輸出?1，

輸入樣例

3

1

2

3

輸出樣例

-1

-1

1

        （1）編程思路，

先對較小的連續n值進行手算，如下，

N=3時，可分解為 1 1 1，乘積最大為1；

N=4時，可分解為1 1 2，乘積最大為2；

N=5時，找不出滿足條件的分解；

N=6時，可分解為 2 2 2，乘積最大為8；

N=7時，找不出滿足條件的分解；

N=8時，可分解為 2 2 4，乘積最大為16；

N=9時，可分解為3 3 3，乘積最大為27；

N=10，N=11時均找不出滿足條件的分解；

        N=12時，可分解為4 4 4，乘積最大為64；當然也可分解為3 3 6，但乘積54，不是最大，

        由此，可以得到如下規律：如果n能整除3（n % 3 == 0），就把n分解成n/3+n/3+n/3；其次如果n能整除4（n % 4 == 0），就分解成n/4+n/4+n/2；其他情況都無解，輸出-1即可，

（2）源程式，

#include <stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        long long n,ans;

        scanf("%lld",&n);

        if (n%3==0)

        {

            ans=(n/3)*(n/3)*(n/3);

            printf("%lld\n",ans);

        }

        else if (n%4==0)

        {

            ans=(n/4)*(n/4)*(n/2);

            printf("%lld\n",ans);

        }

        else

            printf("-1\n");

    }

     return 0;

}

習題45

45-1 余數求和

        本題選自洛谷題庫 （https://www.luogu.org/problem/P2261）

題目描述

給出正整數 n 和k，計算 G(n, k)=k mod 1+k mod 2+k mod 3+?+k mod n 的值，其中k mod i 表示 k 除以 i 的余數，

例如 G(10, 5)= 5 mod 1+5 mod 2+5 mod 3+5 mod 4+5 mod 5?+5 mod 10=0+1+2+1+0+5+5+5+5+5=29

輸入格式

兩個整數n，k

輸出格式

答案

輸入樣例

10 5

輸出樣例

29

        （1）編程思路，

        對于區間[1,n]中的一段連續的子區間[I,j]，如果除k的商相同，那么除k的余數是一個等引數列，這樣每一段的余數都可以快速求出，

        具體方法為：對于k/i=p，找到最大的j，使n/j=p，不難發現，若p=0，則j=n，否則j=k/p，此時，k除以區間[I,j]中每個數的商均為p，余數構成一個等引數列，首項為k%i，尾項為k%j，項數為j-i+1，直接用等引數列求和公式求和，

        （2）源程式，

#include <stdio.h>

int main()

{

    int n,k,i,j;

    scanf("%d%d",&n,&k);

    long long sum=0;

    for (i=1;i<=n;i=j+1)

    {

        int p=k/i;

        if (p==0) j=n;

        else j=k/p<n?k/p:n;

        long long  ai=k%i;

        long long  aj=k%j;

        sum+=(j-i+1)*(ai+aj)/2;

    }

    printf("%lld\n",sum);

    return 0;

}

45-2  燒水問題

        本題選自洛谷題庫 （https://www.luogu.org/problem/P1984）

題目描述

把總質量為1kg的水分裝在n個杯子里，每杯水的質量均為(1/n)kg，初始溫度均為0℃，現需要把每一杯水都燒開，我們可以對任意一杯水進行加熱，把一杯水的溫度升高t℃所需的能量為(4200*t/n)J，其中，“J”是能量單位“焦耳”，如果一旦某杯水的溫度達到100℃，那么這杯水的溫度就不能再繼續升高，此時我們認為這杯水已經被燒開，顯然地，如果直接把水一杯一杯地燒開，所需的總能量為(4200*100)J，

在燒水的程序中，我們隨時可以在兩杯溫度不同的水之間進行熱傳遞操作，熱量只能從溫度較高的那杯水傳遞到溫度較低的那杯水，由于兩杯水的質量相同，所以進行熱傳遞操作之后，原來溫度較高的那杯水所降低的溫度總是等于原來溫度較低的那杯水所升高的溫度，

一旦兩杯水的溫度相同，熱傳遞立刻停止，

為了把問題簡化，我們假設：

1、沒有進行加熱或熱傳遞操作時，水的溫度不會變化，

2、加熱時所花費的能量全部被水吸收，杯子不吸收能量，

3、熱傳遞總是隔著杯子進行，n杯水永遠不會互相混合，

4、熱傳遞符合能量守恒，而且沒有任何的熱量損耗，

在這個問題里，只要求把每杯水都至少燒開一遍就可以了，而不要求最終每杯水的溫度都是100℃，我們可以用如下操作把兩杯水燒開：先把一杯水加熱到100℃，花費能量(4200*100/2)J，然后兩杯水進行熱傳遞，直到它們的溫度都變成50℃為止，最后把原來沒有加熱到100℃的那杯水加熱到100℃，花費能量(4200*50/2)J，此時兩杯水都被燒開過了，當前溫度一杯100℃，一杯50℃，花費的總能量為(4200*75)J，比直接燒開所需的(4200*100)J少花費了25%的能量，

你的任務是設計一個最佳的操作方案使得n杯水都至少被燒開一遍所需的總能量最少，

輸入格式

輸入檔案只有一個數n，

輸出格式

輸出n杯水都至少被燒開一遍所需的最少的總能量，單位為J，四舍五入到小數點后兩位，

輸入樣例

2

輸出樣例

315000.00

          （1）編程思路，

        不妨設每杯水加熱升溫1℃需要消耗1J，并將沸騰溫度100℃簡記為a，則

        第1杯水需要消耗100J的能量，從0℃加熱到a（100℃）；此時第2杯水溫度為a；

        第2杯水需要消耗50J（=1/2*100J）的能量，因為第2杯水可以中和的最高溫度為a/2=100℃/2=50℃，需要加熱升溫a/2（50℃）；此時第1杯水溫度為a/2，第2杯水溫度為a；

        第3杯水需要消耗37.5J（=3/4*50J）的能量，因為第3杯水可以中和的最高溫度為（a/2/2+a）/2=(50℃/2+100℃)/2=62.5℃，需要加熱升溫37.5℃；此時第1杯水為a/4，第2杯水為5*a/8（=62.5℃），第3杯水溫度為a；

        第4杯水需要消耗31.25J（=5/6*37.5J）的能量，因為第4杯水可以中和的最高溫度為((a/4/2+5*a/8)/2+a)/2=11*a/16=68.75℃，需要加熱升溫5*a/16=31.25℃；此時第1杯水為a/8，第2杯水為5*a/16，第3杯水為11*a/16，第4杯水溫度為a；

        ……

由此可推出如下規律，

設第i杯水需要消耗的能量為cost[i]，則有

cost[1]=420000.00/n

cost[2]=(1/2)*cost[1]

cost[3]=(3/4)*cost[2]

cost[4]=(5/6)*cost[3]

    ……   

cost[i+1]= (2*i-1)/(2*i)* cost[i]

        （2）源程式，

#include <stdio.h>

int main()

{

    int n;

    scanf("%d",&n);

    double cost=420000.00/n;

    double sum=0;

    for (int i=1;i<=n;i++)

    {

        sum+=cost;

        cost*=(2*i-1.0)/(2.0*i);

    }

    printf("%.2f\n",sum);

    return 0;

}

45-3  高位與最低位相等

        本題選自洛谷題庫 （https://www.luogu.org/problem/P2110）

題目描述

給定兩個正整數 L 和 R，數出到底有多少個這樣的 X：L <= X <= R，且 X 的最高位與最低位相等（十進制下），比如，2、101、329873可以是這樣的 X，而23、4567就不是，

輸入格式

一行，這一行包括兩個整數 L 和 R（1<=L<=R<=10^18），

輸出格式

一行，這一行包括一個整數，即滿足所述性質的 X 的個數，

輸入樣例

2 47

輸出樣例

12

         （1）編程思路，

        設函式sum（n）求從1到n中合法的X的個數，顯然，當n<=9時，sum（n）=n，

        從10開始，每10個數分一組（10~19，20~29，…，100~109，…，2000~2009，…），每一組中有且只有一個合法的數X，這個很好理解，當最高位確定的時候，最低位有0~9十種情況，但只有與最高位相同的1種符合要求，

        因此，當n>=10時，sum（n）=9+n/10，

        需要特別注意的是，當n的個位數小于最高位的時候，sum(n)要減1，

        例如，當n=4123時，n所處的組（4120~4129）中4124是合法的X，但是取不到，

（2）源程式，

#include <stdio.h>

long long  sum(long long n)

{

    if (n<=9) return n;

    long long a=n%10;

    long long cnt=n/10+9;

    long long b=n;

    while (b>=10) b/=10;

    if (b>a) cnt--;

    return cnt;

}

int main()

{

    long long l,r;

    scanf("%lld%lld",&l,&r);

    printf("%lld",sum(r)-sum(l-1));

    return 0;

}

標籤：C

上一篇：C語言程式設計100例之（44）：分糖果

下一篇：吃頓外賣的時間帶你解決單鏈表問題