牛客网OJ题解--20210311

脸盆大哥的木桶

https://ac.nowcoder.com/acm/problem/14670

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC14670-脸盆大哥的木桶

题目链接

https://ac.nowcoder.com/acm/problem/14670

题目描述

彩虹岛网红脸盆大哥最骄傲就是自己制作的木桶。一天𝑙𝑤𝑞拿了𝑛块木板，其中第𝑖块木板的高度为ℎ𝑖，他希望脸盆大哥能够用这些木板制作出精美的木桶。脸盆大哥告诉𝑙𝑤𝑞制作一个木桶需要𝑘块木板，并且所有桶的底面积为𝑠，底面的木板由𝑠𝑙𝑝提供。𝑙𝑤𝑞想知道用这些木块所制作出来的木桶最多能够盛多少体积的水。
注意，木板不能叠在另一个木板上，且不需要考虑木桶具体是怎么由木板组成的，即是说1块或2块木板也可以组成木桶，底面积仍为𝑠。

输入第一行为一个整数𝑇(2 ≤ 𝑇 ≤ 20)，表示一共有𝑇组测试数据。
对于每组测试数据：
第一行有三个整数𝑛(2 ≤ 𝑛 ≤ 103), 𝑘, 𝑠(1 ≤ 𝑛, 𝑘, 𝑠 ≤ 103)，分别表示木板的数量、制作一个木桶所需要的木板数以及木桶的底面积。
第二行有𝑛个整数，其中第𝑖个整数ℎ𝑖(1 ≤ ℎ𝑖 ≤ 103)代表第𝑖个木板的高度。

对于每组测试数据输出一个整数𝑥，代表用这些木板制作的桶最多能装体积为𝑥的水。

测试样例

输入

输出

20
30

说明

对于第一组样例，第一个桶由第一块木板和第二块木板组成，能够盛水的体积为5，第二个桶由第三块木板和第四块木板组成，能够盛水的体积为15，所以最终体积为20。
对于第二组样例，最后会剩下一块木板无法参与木桶的制作。

解题思路

实际上就是将模板长度从高到低排序，然后每次选k个就组成一个桶，并且用最短的模板来计算体积。看注释很容易就能看懂。

解题代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5;
int a[N];

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k,s;
        cin>>n>>k>>s;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        //排序
        sort(a+1,a+1+n);
        int i=n;
        int ans=0;
        //每一个桶的最小高度分别是下面的i
        for(int i=n-k+1;i>=1;i-=k){
            ans+=a[i]*s;
        }
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

NC15360-银行存款

题目链接

https://ac.nowcoder.com/acm/problem/15360

题目描述

银行的定期存款一般有1年期、2年期、3年期、5年期四种。
现在我们有1块钱，我们想知道，通过合理安排存款方式，n年以后这1块钱最多会变成几块钱。假设在这n年里利率不变，且n年以后这笔钱不能处于2年期、3年期、5年期存款年限的中间（否则会变成活期）。第一行五个数n, r1, r2, r3, r5分别表示年数，1年期年利率，2年期年利率，3年期年利率和5年期年利率。假设我们有1块钱，i年期存款到期后这1块钱会变成（1 + ri)i块钱。1 <= n <= 20 且 n为整数，0.04 <= r1 <= r2 <= r3 <= r5 <= 0.05。一行一个数表示答案。保留5位小数(绝对误差或相对误差在1e-5之内的结果均判断为通过)。

测试样例

输入

8 0.0430 0.0449 0.0458 0.0473

输出

1.44112

解题思路

就是一个简单的dp，对于这种前面状态决定后面状态的题，基本上就是打表dp，但是难点还是在于找到递推式，很遗憾，这次没找到，作为积累吧。

解题代码

#include <bits/stdc++.h>

#define ll long long
using namespace std;

double max(double a, double b)
{
    if (a > b)
        return a;
    else
        return b;
}
double dp[40];
int main()
{
    int n;
    double r1, r2, r3, r5;
    cin >> n >> r1 >> r2 >> r3 >> r5;
    r1 = pow(1 + r1, 1);
    r2 = pow(1 + r2, 2);
    r3 = pow(1 + r3, 3);
    r5 = pow(1 + r5, 5);
    dp[0] = 1;
    //dp打表yyds
    for (int i = 1; i <= 20; ++i)
    {
        if (i >= 1)
            dp[i] = max(dp[i - 1] * r1, dp[i]);
        if (i >= 2)
            dp[i] = max(dp[i - 2] * r2, dp[i]);
        if (i >= 3)
            dp[i] = max(dp[i - 3] * r3, dp[i]);
        if (i >= 5)
            dp[i] = max(dp[i - 5] * r5, dp[i]);
    }
    cout << dp[n] << endl;
    system("pause");
    return 0;
}