LOADING STUFF...

题解 CF588A 【Duff and Meat】

技术分享4年前 (2020)更新 技术分享
1,737 0 0

题意

有一个人,想吃 $n$ 天肉,第 $i$ 天需要吃 $a[i]$ 块肉,第 $i$ 天超市肉价为每块 $b[i]$ 元,买来的肉可以留到后面吃,求这个人在每天都吃到肉的情况下花费的最小值。

题目标签:贪心

思路

一边输入一边计算,每次记录下最低价格,即 $mini=min(mini,b[i])$ 然后乘以每天所需要的肉的数量。即 $ans+=mini\times a[i]$ 。

代码段:

比较容易实现

for(int i=0;i<n;i++) {
	cin>>a[i]>>b[i];
    mini=min(mini,b[i]);  // 每次比较出最小肉价
    ans+=mini*a[i]; // 加上需要花的钱
}

如果你追求最优解,可以在内存上进行优化,将数组改为变量。

for(int i=0;i<n;i++) {
    cin>>a>>b; // 数组改为变量
    mini=min(mini,b);
    ans+=mini*a;
}
© 版权声明

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...