# 14093: 【原4093】Candy

### 题目描述

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

7 3
5 10
2 5
3 6

62

## 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;
}