6 条题解
-
13
鳗鱼:Eel 鳗鱼富含多种营养成分,具有补虚养血、祛湿、抗痨等功效,是久病、虚弱、贫血、肺结核等病人的良好营养品。 哈哈,言归正传,这道题的贪心思路管理员和众位同学讲的已经很详细了,在此不再赘述,这篇题解主要补充了输入输出格式,并提供了分解代码,AC代码放到了最后
题目描述
题目描述
乌拉乎在为开设鳗鱼火锅店作准备。现在,他想到一个有鳗鱼的池塘把弄回n条鳗鱼。把第 i 条鳗鱼从池塘弄回小店需要 ti 个单位的时间。随着时间的推移,乌拉乎它们弄回来所消耗的体力与时间成正比,即在第 t 时刻开始运第 i 条鳗鱼所消耗的体力为 t∗ci ,其中,ci 是给定的常数。一开始是从 t=0 时刻开始,也就是说运送第一条八目鳗所消耗的体力为 0 。
乌拉乎想知道把所有鳗鱼运回小店所消耗的体力最少是多少
输入输出格式
输入格式
第一行一个整数n,表示鳗鱼的数量
接下来n行,每行两个整数t和c, 表示运鳗鱼的时间和功率
输出格式
一个整数,表示最少需要的体力
核心代码
bool cmp(Eel x,Eel y) { return x.t * y.c < y.t * x.c; }
for (int i = 1;i <= n;i++) { ans += now * a[i].c; now += a[i].t; }
温馨提示
ans要开long long,不然会70分的。
完整代码实现
#include <bits/stdc++.h> using namespace std; struct Eel { int t,c; }a[10005]; bool cmp(Eel x,Eel y) { return x.t * y.c < y.t * x.c; } int n; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i].t >> a[i].c; } sort(a+1,a+n+1,cmp); long int now = 0,ans = 0; for (int i = 1;i <= n;i++) { ans += now * a[i].c; now += a[i].t; } cout << ans; return 0; }//已AC
结语
题解制作艰难,请点赞支持一下~ -
13
这个问题可以通过贪心算法来解决。我们希望选择一部分鳗鱼进行烤制,以获得最大的总能量。
首先,我们需要读取输入数据。第一行包含一个整数n,表示鳗鱼的数量。接下来的n行中,每行包含两个整数,分别表示每条鳗鱼的能量和所需时间。
然后,我们创建一个vector来保存每条鳗鱼的能量和时间,并根据特定规则对其进行排序。根据提示,我们可以选择按照功率密度(能量/时间)从小到大的顺序进行排序。这样可以确保我们优先选取功率密度较低的鳗鱼,以最大化获得总能量。
排序完成后,我们使用一个变量来记录当前的时间和累计的总能量。然后,依次遍历排序后的鳗鱼列表,将当前鳗鱼的能量乘以累计的时间加到总能量上,然后更新当前时间为当前时间加上鳗鱼的所需时间。
最后,输出总的能量即可。
以下是整个算法的步骤:
- 读取输入数据,包括n和每条鳗鱼的能量和所需时间。
- 根据功率密度从小到大对鳗鱼进行排序。
- 使用变量记录当前时间和累计的总能量。
- 遍历排序后的鳗鱼列表,将当前鳗鱼的能量乘以累计的时间加到总能量上,并更新当前时间为当前时间加上鳗鱼的所需时间。
- 输出总的能量。
贪心算法的关键在于选择合适的排序规则和在每一步中做出当前状态下的最优选择。在这个问题中,选择按照功率密度进行排序,是一个很好的策略,能够得到最优解。
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool compare(const pair<int, int>& a, const pair<int, int>& b) { return a.first * b.second < b.first * a.second; } int main() { int n; cin >> n; vector<pair<int, int>> eels(n); for (int i = 0; i < n; i++) { cin >> eels[i].first >> eels[i].second; } sort(eels.begin(), eels.end(), compare); long long totalEnergy = 0; long long currentTime = 0; for (int i = 0; i < n; i++) { totalEnergy += currentTime * eels[i].second; currentTime += eels[i].first; } cout << totalEnergy << endl; return 0; }
点赞!!!o( ̄▽ ̄)d 点赞!!!o( ̄▽ ̄)d 点赞!!!o( ̄▽ ̄)d
-
3
-题目回顾-
乌拉乎在为开设鳗鱼火锅店作准备。现在,他想到一个有鳗鱼的池塘把弄回n条鳗鱼。把第条鳗鱼从池塘弄回小店需要个单位的时间。随着时间的推移,乌拉乎它们弄回来所消耗的体力与时间成正比,即在第时刻开始运第条鳗鱼所消耗的体力为,其中是给定的常数。一开始是从时刻开始,也就是说运送第一条八目鳗所消耗的体力为 0 。 乌拉乎想知道把所有鳗鱼运回小店所消耗的体力最少是多少
-题目分析-
求出cmp函数排序规则:即可
-代码-
#include <bits/stdc++.h>//BY AGOMG using namespace std; struct Fish{ int t, c; }fish[10005]; long long n, ans; bool cmp(Fish x, Fish y){ return x.t * y.c < x.c * y.t;//排序规则 } int main() { cin >> n; for (int i = 0; i < n; i++){ cin >> fish[i].t >> fish[i].c; } sort(fish, fish + n, cmp); int t = 0; for (int i = 0; i < n; i++){ ans += fish[i].c * t; t += fish[i].t;//时间增加 } cout << ans; }
-
0
MAN , WHAT CAN I SAY? MANBA OUT!
#include <iostream> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; // struct Man//MAN! WHAT CAN I SAY?! MANBA OUT! { ll t,c; } m[10005]; ll n,ans,t_now; // bool cmp(Man x,Man y) { return x.t * y.c < y.t * x.c; } int main() { cin>>n; for (ll i=1;i<=n;i++) { cin>>m[i].t>>m[i].c; } sort(m+1,m+n+1,cmp); for (ll i=1;i<=n;i++) { ans+=t_now*m[i].c; t_now+=m[i].t; } cout<<ans; return 0; }
本人喜欢把代码分成:
头文件+其他 定义变量 函数 因为好看……
-
0
😄
Very easy sir.
#include using namespace std; int n; long long sum; struct M { int t,c; }q[10005]; bool cmp(M x,M y) { return x.c*y.t>y.c*x.t; 👀️ //由x.c*(t+y.t)+y.c*t>x.c*t+y.c*(t+x.t)衍生而来 } int main() { cin>>n; for(int i=1;i<=n;i++)cin>>q[i].t>>q[i].c; sort(q+1,q+n+1,cmp); int t=0; for(int i=1;i<=n;i++) { sum+=t*q[i].c; t+=q[i].t; } cout<<sum; return 0; }
- 1
信息
- ID
- 261
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 692
- 已通过
- 371
- 上传者