牛客寒假6-C.项链

链接：https://ac.nowcoder.com/acm/contest/332/C

题意：

小B想给她的新项链染色。
现在有m种颜色，对于第i种颜色，小B有a_i单位的颜料，每单位颜料可以染项链的一个珠子；
同时，小B对于第i种颜色的喜爱度为b_i。
已知项链有n个珠子，求染色后每个珠子的颜色的喜爱度之和的最大值。
(每个珠子只能至多被染一次，不被染色则喜爱度为0)

思路：

贪心即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 10;

struct Node
{
    int _a;
    int _b;
    bool operator < (const Node & that) const {
        return this->_b > that._b;
    }
}node[MAXN];

int main()
{
    int n, m;
    LL all = 0;
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= m;i++)
        cin >> node[i]._a,all += node[i]._a;
    for (int i = 1;i <= m;i++)
        cin >> node[i]._b;
    sort(node + 1, node + 1 + m);
    LL res = 0;
    int w = 1;
    while (n > 0 && all > 0)
    {
        if (n >= node[w]._a)
        {
            res += node[w]._a * node[w]._b;
            n -= node[w]._a;
            all -= node[w]._a;
            w++;
        }
        else
        {
            res += n * node[w]._b;
            break;
        }
    }
    cout << res << endl;

    return 0;
}

巴特西

牛客寒假6-C.项链

链接：https://ac.nowcoder.com/acm/contest/332/C

题意：

思路：

代码：

最新文章

热门文章