题解：CF2038L Bridge Renovation

__czy · 2024-12-01 13:58:02 · 题解

题目链接

题目大意

已知一个木块的长度是60，问你怎么拆可以用最少得木条拆出n个18，n个21，n个25的小木条。

思路

我们很容易发现当最优方案一定是以下3种，其他方法一定比这3种要劣。

• 方案一：2根21和1根18
• 方案二：2根25
• 方案三：3根18

我们能够发现7根长度为60的木条正好可以裁出6根25,6根21和6根18。方案为3次方案一，3次方案二和1次方案三

则对于每6组木板，我们都会使用7根长度为60的木板，且这一定是最优的。

接下来考虑剩下的1~5组模板的数量，模拟可以得到：

• 裁出1组需要2根
• 裁出2组需要3根
• 裁出3组需要4根
• 裁出4组需要5根
• 裁出5组需要6根

我们可以把上述结果预处理成一个数组a，则我们输出是只需要输出 \lfloor \frac{n}{6} \rfloor + a[n mod 6]。

代码实现

#include<iostream>
#include<cstdio>

using namespace std;

int n,a[10];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int main()
{
    n=read();
    a[1]=2;
    a[2]=3;
    a[3]=4;
    a[4]=5;
    a[5]=6;//预处理剩余1,2,3,4,5根时需要的木条数量 
    cout<<n/6*7+a[n%6];//输出n/6*7+a[n%6],当n=6时，默认+0，不会影响结果 
    return (0^0);
}

完结撒花~~~

本人第1篇题解，望通过。