算法笔记day08

1.游游的水果大礼包

 这道题很容易让人想到贪心，但是其实是一道枚举题，只需举一个反例，贪心无非就是哪个礼包价值大，就优先组成哪个礼包。

算法思路：

设可以组成x个a礼包，y个b礼包，求ax + by的最大值，只需枚举x,y的所有情况，在所有情况中挑一个最大值。

x的取值范围就是[0, min(2/n, m)] y的取值范围是[0, min(n,2/m)]

#include <iostream>typedef long long ll;using namespace std;
int main()
{ll n ,m, a, b;cin >> n >> m >> a >> b;ll mx =min(n / 2 , m); long long ret = 0;for(ll x = 0; x <= mx; x++)//枚举a礼包个数{ll y = min(n - (2 * x), (m - x)/2);//计算b礼包个数ret = max(ret,a * x + b * y );}cout << ret << endl;return 0;
}

2.买卖股票的最好时机(二)_牛客题霸_牛客网

算法思路：

这道题只需要意识到一个问题，

假设输入是[1,2,3,4,5,6]，我一天买第二天卖，和我第一天买最后一天卖的收益是一样的。

将每一天的涨跌都记录下来，将所有涨价，都加在一起就是，最大的收益。

#include <iostream>
using namespace std;int main() 
{int n = 0;cin >> n;int price[n];for(int i = 0; i < n; i++){cin >> price[i];}int sum[n];//记录每日的涨价和跌价int ret = 0;for(int i = 1; i < n; i++){sum[i-1] = price[i] - price[i-1];if(sum[i-1] > 0){ret += sum[i-1];}}cout << ret << endl;return 0;
}
// 64 位输出请用 printf("%lld")