23.6 แบบฝึกหัด

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, q;
    cin >> k >> q;
    vector<long long> coins(k);
    for (int i = 0; i < k; i++) {
        cin >> coins[i];
    }
    sort(coins.rbegin(), coins.rend());
    for (int j = 0; j < q; j++) {
        long long amount;
        cin >> amount;
        long long total = 0;
        for (int i = 0; i < k; i++) {
            total += amount / coins[i];
            amount %= coins[i];
        }
        cout << total << '\n';
    }
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long gap;
    cin >> n >> gap;
    vector<pair<long long, long long>> films(n);
    for (int i = 0; i < n; i++) {
        long long start, finish;
        cin >> start >> finish;
        films[i] = {finish, start};
    }
    sort(films.begin(), films.end());
    int count = 0;
    long long ready = 0;
    for (int i = 0; i < n; i++) {
        long long finish = films[i].first;
        long long start = films[i].second;
        if (start >= ready) {
            count++;
            ready = finish + gap;
        }
    }
    cout << count << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long capacity;
    cin >> n >> capacity;
    vector<pair<long long, long long>> fruit(n);
    for (int i = 0; i < n; i++) {
        cin >> fruit[i].first >> fruit[i].second;
    }
    sort(fruit.begin(), fruit.end(), [](const pair<long long, long long> &a, const pair<long long, long long> &b) {
        return a.second * b.first > b.second * a.first;
    });
    long long room = capacity, whole = 0;
    double part = 0;
    for (int i = 0; i < n && room > 0; i++) {
        long long grams = fruit[i].first, price = fruit[i].second;
        if (grams <= room) {
            whole += price;
            room -= grams;
        } else {
            part = (double)price * room / grams;
            room = 0;
        }
    }
    cout << fixed << setprecision(2) << whole + part << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long limit;
    cin >> n >> limit;
    vector<long long> weight(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    sort(weight.begin(), weight.end());
    int light = 0, heavy = n - 1, boats = 0;
    while (light <= heavy) {
        if (light < heavy && weight[light] + weight[heavy] <= limit) {
            light++;
        }
        heavy--;
        boats++;
    }
    cout << boats << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> students(n);
    for (int i = 0; i < n; i++) {
        int first_day, last_day;
        cin >> first_day >> last_day;
        students[i] = {last_day, first_day};
    }
    sort(students.begin(), students.end());
    int sessions = 0, last_session = 0;
    for (int i = 0; i < n; i++) {
        if (students[i].second > last_session) {
            sessions++;
            last_session = students[i].first;
        }
    }
    cout << sessions << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<long long> minutes(n);
    for (int i = 0; i < n; i++) {
        cin >> minutes[i];
    }
    sort(minutes.begin(), minutes.end(), greater<long long>());
    long long total = 0;
    for (int j = 0; j < n; j++) {
        total += minutes[j] * (j / k);
    }
    cout << total << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> piles;
    for (int i = 0; i < n; i++) {
        long long weight;
        cin >> weight;
        piles.push(weight);
    }
    long long cost = 0;
    while (piles.size() > 1) {
        long long a = piles.top();
        piles.pop();
        long long b = piles.top();
        piles.pop();
        cost += a + b;
        piles.push(a + b);
    }
    cout << cost << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<pair<long long, long long>> tasks(n);
    for (int i = 0; i < n; i++) {
        long long days, due;
        cin >> days >> due;
        tasks[i] = {due, days};
    }
    vector<long long> exams(k);
    for (int i = 0; i < k; i++) {
        cin >> exams[i];
    }
    sort(tasks.begin(), tasks.end());
    sort(exams.begin(), exams.end());
    long long worked = 0, worst = 0;
    int passed = 0;
    for (int i = 0; i < n; i++) {
        worked += tasks[i].second;
        while (passed < k && exams[passed] <= worked + passed) {
            passed++;
        }
        long long finish = worked + passed;
        worst = max(worst, finish - tasks[i].first);
    }
    cout << worst << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long per_day;
    cin >> n >> per_day;
    vector<pair<long long, long long>> jobs(n);
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].first >> jobs[i].second;
    }
    sort(jobs.begin(), jobs.end());
    priority_queue<long long, vector<long long>, greater<long long>> kept;
    long long total = 0;
    for (int i = 0; i < n; i++) {
        kept.push(jobs[i].second);
        total += jobs[i].second;
        if ((long long)kept.size() > per_day * jobs[i].first) {
            total -= kept.top();
            kept.pop();
        }
    }
    cout << total << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string digits;
    cin >> n >> k >> digits;
    string kept;
    for (char c : digits) {
        while (k > 0 && !kept.empty() && kept.back() > c) {
            kept.pop_back();
            k--;
        }
        kept.push_back(c);
    }
    while (k > 0) {
        kept.pop_back();
        k--;
    }
    int start = 0;
    while (start + 1 < (int)kept.size() && kept[start] == '0') {
        start++;
    }
    cout << kept.substr(start) << '\n';
    return 0;
}