Skip to content

14093: 【原4093】Candy

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4093

Description

有一天,xyy来到了一间糖果屋。他发现糖果屋里有\(M\)箱糖果,第\(i\)箱糖果中,装有\(A_i\)袋糖果,且该箱中每袋糖果中都含有\(B_i\)颗糖。xyy可高兴了,然而这时屋里响起了一个声音:“做人不能太贪婪了,你最多只能带\(N\)袋糖果离开。”xyy开始方了,他想问你他最多可以带多少糖果离开?

Input Format

第一行两个整数\(N,M\),如题意。

接下来$M$行,每行两个整数\(A_i,B_i\),表示第\(i\)箱糖果里装了\(A_i\)袋糖果,且每袋装有\(B_i\)颗糖。

Output Format

输出一行,表示答案。

Sample Input

7 3
5 10
2 5
3 6

Sample Output

62

Data Range

对于\(20\%\)的数据,\(M \le 3\)。

对于\(30\%\)的数据,\(M \le 100\)。

对于\(60\%\)的数据,\(M \le 2000\)。

对于\(100\%\)的数据,\(1 \le N \le 10^9\),\(0 \le M,A_i,B_i \le 2 \times 10^5\)。

FineArtz's solution

/* Candy */
#include <iostream>
using namespace std;

class Node{
public:
    int pack = 0, candy = 0;

    Node() = default;
    Node(int p, int c) : pack(p), candy(c) {}

    bool operator <(const Node &n){
        return candy < n.candy;
    }
};

class Heap{
public:
    Node a[200005];
    int heapsize = 0;

    void swap(int x, int y){
        Node t = a[x];
        a[x] = a[y];
        a[y] = t;
    }

    void siftup(int x){
        while (x > 1){
            if (a[x / 2] < a[x]){
                swap(x, x / 2);
                x /= 2;
            }
            else
                break;
        }
    }

    void siftdown(){
        int i = 2;
        while (i <= heapsize){
            if (i + 1 <= heapsize && a[i] < a[i + 1])
                ++i;
            if (a[i / 2] < a[i]){
                swap(i, i / 2);
                i *= 2;
            }
            else
                break;
        }
    }

    void insert(const Node &n){
        a[++heapsize] = n;
        siftup(heapsize);
    }

    void remove(){
        swap(1, heapsize);
        --heapsize;
        siftdown();
    }

    Node getMax(){
        return a[1];
    }
};

Heap heap;
int n, m;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >> y;
        heap.insert(Node(x, y));
    }
    long long ans = 0;
    while (n != 0 && heap.heapsize != 0){
        Node t = heap.getMax();
        if (n < t.pack){
            ans += n * (long long)t.candy;
            break;
        }
        else{
            ans += (long long)t.pack * t.candy;
            n -= t.pack;
            heap.remove();
        }
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include <iostream>
using namespace std;

const int MAX = 200001;
int n, m;
struct candy {
    int ai = 0;
    int bi = 0;
}c[MAX];

long long nums[MAX] = { 0 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> c[i].ai;
        cin >> c[i].bi;
        nums[c[i].bi] += c[i].ai;
    }
    long long ans = 0;

    for (long long i = MAX - 1; i >= 0; --i) {
        if (n > nums[i]) {
            ans += nums[i] * i;
            n -= nums[i];
        }
        else {
            ans += n * i;
            break;
        }
    }
    cout << ans;
    return 0;
}

WashSwang's solution

#include <cstdio>
using namespace std;
int m,a,b;
long long n,ans,num[200001];
int main() {
    scanf("%lld%d",&n,&m);
    for (int i=0;i<m;++i){
        scanf("%d%d",&a,&b);
        num[b]+=a;
    }
    for (int i=200000;i>=1;--i)
    {
        if (n>=num[i]) {
            ans += num[i] * i;
            n -= num[i];
        }
        else{
            ans+=n*i;
            break;
        }
    }
    printf("%lld",ans);
    return 0;
}

yyong119's solution

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_M = 200010;
struct box{
    int pack, num;
}boxes[MAX_M];
int n, m, cnt;
long long ans;

bool cmp(const box &a, const box &b) {
    return a.num > b.num;
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) scanf("%d%d", &boxes[i].pack, &boxes[i].num);
    sort(boxes, boxes + m, cmp);
    for (int i = 0; i < m; ++i)
        if (boxes[i].pack <= n) {
            n -= boxes[i].pack;
            ans += (long long) boxes[i].pack * boxes[i].num;
        } else {
            ans += (long long) n * boxes[i].num;
            break;
        }
    printf("%lld\n", ans);
    return 0;
}