牛牛炒股票

[编程题]牛牛炒股票

热度指数：429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。
接下来N行，每行包含两个正整数，表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。
每只股票可以买入多股，但必须是整数。

输出描述:

输出一个整数表示牛牛最多能赚的钱数。

示例1

输入

输出

算法知识视频讲解

黑莓婆婆

背包

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> dp(M + 1);  // dp[i] 表示投资 i 元最多赚多少钱
    while (N--) {
        int X, Y, d;
        cin >> X >> Y;
        d = Y - X;
        if (d <= 0) continue;
        for (int i = X; i <= M; i++) {
            dp[i] = max(dp[i], dp[i - X] + d);
        }
    }
    cout << dp[M] << endl;
    return 0;
}

发表于 2021-08-10 20:54:09 回复(0)

C/C++

pein531

多重背包的模板问题，用二进制来优化

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> dp(m + 1);
    vector<PII> goods;
    // 多重背包求解
    for(int i = 0; i < n; i++) {
        int v, w;
        scanf("%d%d", &v, &w);
        int s = m / v;
        w -= v;
        for(int k = 1; k <= s; k <<= 1) {
            goods.push_back({k*v, k*w});
            s -= k;
        }
        if(s > 0) goods.push_back({s*v, s*w});
    }
    for(auto good: goods) {
        for(int j = m; j >= good.first; j--) {
            dp[j] = max(dp[j], dp[j - good.first] + good.second);
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

发表于 2023-02-07 15:12:23 回复(0)

找个工作也太难了

这道题的测试用例是不是有问题啊，读入股票信息的时候出现了异常

编辑于 2021-08-13 16:28:20 回复(1)

牛客414045068号

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int find(vector<int> num, int mm)
{
for(int i=0;i<num.size();i++)
{
if(mm>num[i])
{
return i;
}
}
return -1;
}

int main() {
int a,b;
int N,M;
int n=1;
vector<int> today;
vector<int> nextday;
while(scanf("%d %d",&a, &b) != EOF)
{
if(n==1)
{
N=a;
M=b;
}
else{
today.push_back(a);
nextday.push_back(b);
}
n++;
}

int tvar;
    for (int i = 0; i<today.size()-1; i++)
        for (int j = i + 1; j<today.size(); j++)
        {
float n1=nextday[j]/float(today[j]);
float n2=nextday[i]/float(today[i]);
            if ( n1> n2)
            {
                tvar = today[j];
                today[j] = today[i];
                today[i] = tvar;

tvar = nextday[j];
                nextday[j] = nextday[i];
                nextday[i] = tvar;
            }
        }
if((nextday[0]/float(today[0]))<1)
{
printf("%d",0);
}
else
{
int min=today[0];
for (int i = 0; i<today.size(); i++)
{
if(today[i]<min)
min=today[i];
}

vector<int> xuhao;
vector<int> gounum;

for(int i=0;M>=min;i++)
{
if(M>=today[i])
{
int qq=M/today[i];
M=M%today[i];
xuhao.push_back(i);
gounum.push_back(qq);
}
}
int shouyi=0;
for(int i=0;i<xuhao.size();i++)
{
int list=xuhao[i];
shouyi+=(nextday[list]-today[list])*gounum[i];
}
printf("%d",shouyi);
}
return 0;
}

发表于 2021-07-27 20:53:34 回复(0)