牛客网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)代表第𝑖个木板的高度。
对于每组测试数据输出一个整数𝑥,代表用这些木板制作的桶最多能装体积为𝑥的水。
测试样例
输入
2 4 2 5 1 2 3 4 5 2 5 1 4 5 2 3
输出
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; }