J-L25 贪心¶

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

// 规范币制找零：优先用大面额，兑换后 n 一定能被剩余面额凑出
int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int v : {10, 5, 2, 1}) {
        cnt += n / v;
        n %= v;
    }
    cout << cnt << endl;
    return 0;
}

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

// 反例币制找零：面额 {7,5,1}，「优先大面额」的贪心不再保证最优
int main() {
    int n;
    cin >> n;
    int g = n, gcnt = 0;                    // 小 X 的收银程序：贪心
    for (int v : {7, 5, 1}) {
        gcnt += g / v;
        g %= v;
    }
    // 真正最少张数：三重循环枚举三种面额各用几张
    int best = n + 1;
    for (int a = 0; a * 7 <= n; a++)
        for (int b = 0; a * 7 + b * 5 <= n; b++) {
            int rest = n - a * 7 - b * 5;
            best = min(best, a + b + rest);
        }
    cout << gcnt << "\n" << best << "\n" << (gcnt == best ? "OK" : "FAIL") << "\n";
    return 0;
}

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

int main() {
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> p(n);
    for (auto &x : p) cin >> x;
    sort(p.begin(), p.end());
    long long sum = 0;
    int cnt = 0;
    for (auto x : p) {
        if (sum + x > m) break;
        sum += x;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

// P1208 混合牛奶：单价低的奶农先买满
int main() {
    long long n;
    int m;
    cin >> n >> m;
    vector<pair<long long, long long>> f(m);   // (单价, 产量)
    for (auto& p : f) cin >> p.first >> p.second;
    sort(f.begin(), f.end());
    long long cost = 0;
    for (auto& p : f) {
        long long take = min(n, p.second);
        cost += take * p.first;
        n -= take;
        if (n == 0) break;
    }
    cout << cost << endl;
    return 0;
}

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

// P2240 部分背包：金币可分割，按单位价值从高到低装
int main() {
    int n;
    double t;
    cin >> n >> t;
    vector<pair<double, double>> a(n);         // (单位价值, 重量)
    for (auto& p : a) {
        double m, v;
        cin >> m >> v;
        p = {v / m, m};
    }
    sort(a.rbegin(), a.rend());
    double ans = 0;
    for (auto& p : a) {
        double take = min(t, p.second);
        ans += take * p.first;
        t -= take;
        if (t <= 0) break;
    }
    printf("%.2f\n", ans);
    return 0;
}

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

// P1478 陶陶摘苹果升级版：够得着的苹果里，挑力气花费最小的先摘
int main() {
    int n, s, a, b;
    cin >> n >> s >> a >> b;
    int reach = a + b;
    vector<int> cost;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (x <= reach) cost.push_back(y);
    }
    sort(cost.begin(), cost.end());
    int cnt = 0;
    for (int c : cost) {
        if (s < c) break;
        s -= c;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<long long> x(n);
    for (auto &v : x) cin >> v;
    sort(x.begin(), x.end());
    // 中位数最优：把仓库放在中间那家店，两侧偏移互相抵消
    long long best = x[(n - 1) / 2], total = 0;
    for (auto v : x) total += llabs(v - best);
    cout << total << endl;
    return 0;
}

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

// P1181 数列分段 Section I：顺序装箱，装不下就另起一段
int main() {
    int n;
    long long m;
    cin >> n >> m;
    int cnt = 1;
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (cur + x <= m) cur += x;
        else { cnt++; cur = x; }
    }
    cout << cnt << endl;
    return 0;
}

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

// P1223 排队接水：短作业优先（交换论证可证），同时间小编号在前
int main() {
    int n;
    cin >> n;
    vector<pair<long long, int>> t(n);         // (接水时间, 编号)
    for (int i = 0; i < n; i++) {
        cin >> t[i].first;
        t[i].second = i + 1;
    }
    sort(t.begin(), t.end());
    double sum = 0, wait = 0;
    for (int i = 0; i < n; i++) {
        cout << t[i].second << " \n"[i == n - 1];
        sum += wait;                            // 第 i 个人等前面所有人接完
        wait += t[i].first;
    }
    cout << fixed << setprecision(2) << sum / n << "\n";
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for (auto &x : s) cin >> x;
    // 交换论证：两个串 a、b，谁拼在前面大就谁在前——比较 a+b 与 b+a
    sort(s.begin(), s.end(), [](const string &a, const string &b) {
        return a + b > b + a;
    });
    string ans;
    for (auto &x : s) ans += x;
    cout << ans << endl;
    return 0;
}

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

// P4995 跳跳！：排序后「最高→最低→次高→次低」交替跳，每步落差最大
int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (auto& x : h) cin >> x;
    sort(h.begin(), h.end());
    long long total = 0, cur = 0;              // cur 从地面 0 出发
    int i = 0, j = n - 1;
    bool big = true;
    while (i <= j) {
        long long nxt = big ? h[j--] : h[i++];
        total += (nxt - cur) * (nxt - cur);
        cur = nxt;
        big = !big;
    }
    cout << total << endl;
    return 0;
}

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

// P1056 排座椅：横纵通道独立统计各自能隔开多少对，取前 k/l 大
int rowCnt[1005], colCnt[1005];

int main() {
    int m, n, k, l, d;
    cin >> m >> n >> k >> l >> d;
    for (int i = 0; i < d; i++) {
        int x, y, p, q;
        cin >> x >> y >> p >> q;
        if (x == p) colCnt[min(y, q)]++;       // 同行相邻 → 在两列之间开竖通道
        else rowCnt[min(x, p)]++;              // 同列相邻 → 在两行之间开横通道
    }
    vector<pair<int, int>> rows, cols;         // (隔开对数, 位置)
    for (int i = 1; i < m; i++) if (rowCnt[i]) rows.push_back({rowCnt[i], i});
    for (int j = 1; j < n; j++) if (colCnt[j]) cols.push_back({colCnt[j], j});
    sort(rows.rbegin(), rows.rend());
    sort(cols.rbegin(), cols.rend());
    vector<int> ra, ca;
    for (int i = 0; i < k && i < (int)rows.size(); i++) ra.push_back(rows[i].second);
    for (int i = 0; i < l && i < (int)cols.size(); i++) ca.push_back(cols[i].second);
    sort(ra.begin(), ra.end());
    sort(ca.begin(), ca.end());
    for (int i = 0; i < (int)ra.size(); i++) cout << ra[i] << " \n"[i == (int)ra.size() - 1];
    if (ra.empty()) cout << "\n";
    for (int i = 0; i < (int)ca.size(); i++) cout << ca[i] << " \n"[i == (int)ca.size() - 1];
    if (ca.empty()) cout << "\n";
    return 0;
}

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

// P1106 删数问题：每轮删掉「第一个下降位」的数字，剩 k 轮
int main() {
    string s;
    int k;
    cin >> s >> k;
    while (k--) {
        int i = 0;
        while (i + 1 < (int)s.size() && s[i] <= s[i + 1]) i++;
        s.erase(i, 1);                          // 全程递增则删末位
    }
    while (s.size() > 1 && s[0] == '0') s.erase(0, 1);   // 去前导零
    if (s.empty()) s = "0";
    cout << s << endl;
    return 0;
}

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

int main() {
    string s;
    int k;
    cin >> s >> k;
    int rem = (int)s.size() - k;   // 还可以丢弃的字符数
    string st;                     // 栈：保留的数字（保持原相对次序）
    for (char c : s) {
        // 栈顶比当前数字小还舍得丢吗？丢掉它能让高位变大
        while (!st.empty() && rem > 0 && st.back() < c) {
            st.pop_back();
            rem--;
        }
        st.push_back(c);
    }
    // 若一路递增没丢够，把末尾多余的截掉
    cout << st.substr(0, k) << endl;
    return 0;
}

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

// P1094 纪念品分组：排序后最贵 + 最便宜配对，配不上则最贵的独占一组
int main() {
    int w, n;
    cin >> w >> n;
    vector<int> p(n);
    for (auto& x : p) cin >> x;
    sort(p.begin(), p.end());
    int i = 0, j = n - 1, cnt = 0;
    while (i <= j) {
        if (i < j && p[i] + p[j] <= w) i++;    // 最便宜的能搭最贵的就带上
        j--;                                    // 最贵的无论如何都占一组
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

// P1803 线段覆盖：按结束时间排序，结束早的先参加（活动选择经典）
int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);               // (结束时间, 开始时间)
    for (auto& p : v) cin >> p.second >> p.first;
    sort(v.begin(), v.end());
    int cnt = 0, last = -1;
    for (auto& p : v) {
        if (p.second >= last) { cnt++; last = p.first; }
    }
    cout << cnt << endl;
    return 0;
}

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

int main() {
    int n;
    long long L;
    cin >> n >> L;
    vector<pair<long long, long long>> seg(n);
    for (auto& s : seg) cin >> s.first >> s.second;
    sort(seg.begin(), seg.end());           // 按左端点排序
    long long cur = 0;                      // 已覆盖 [0, cur]
    int cnt = 0;
    for (int i = 0; i < n && cur < L; ) {
        if (seg[i].second <= cur) { i++; continue; }    // 整条被盖住，跳过
        if (seg[i].first > cur) break;                   // 与已覆盖区断档：无解
        long long reach = cur;                           // 左端点 ≤ cur 的线段里挑右端点最远的
        while (i < n && seg[i].first <= cur) {
            reach = max(reach, seg[i].second);
            i++;
        }
        cur = reach;
        cnt++;
    }
    if (cur < L) cout << -1 << "\n";
    else cout << cnt << "\n";
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> seg(n);   // {左端点, 右端点}
    for (auto &[l, r] : seg) cin >> l >> r;
    // 按右端点从小到大：箭放在当前未被引爆区间的右端点，
    // 能把它和后面所有左端点 <= 该点的区间一起引爆
    sort(seg.begin(), seg.end(), [](auto &a, auto &b) {
        return a.second < b.second;
    });
    int cnt = 0;
    long long cur = LLONG_MIN;   // 上一支箭的位置
    for (auto &[l, r] : seg) {
        if (l > cur) {           // 这支箭够不着它，需要一支新箭
            cnt++;
            cur = r;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> seg(n);   // {结束时间, 开始时间}
    for (auto &[e, s] : seg) cin >> s >> e;
    // 按结束时间排序，能留下就留下（活动选择），最少移走 = n - 最多留下
    sort(seg.begin(), seg.end());
    long long lastEnd = LLONG_MIN;
    int kept = 0;
    for (auto &[e, s] : seg) {
        if (s >= lastEnd) {   // 与已选区间不重叠（端点相接允许）
            kept++;
            lastEnd = e;
        }
    }
    cout << n - kept << endl;
    return 0;
}

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

// P1209 修理牛棚：先用一整块盖住所有牛，再把最大的 m-1 个空隙断开
int main() {
    int m, s, c;
    cin >> m >> s >> c;
    vector<int> a(c);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    int total = a[c - 1] - a[0] + 1;
    vector<int> gap;
    for (int i = 1; i < c; i++) gap.push_back(a[i] - a[i - 1] - 1);
    sort(gap.rbegin(), gap.rend());
    for (int i = 0; i < m - 1 && i < (int)gap.size(); i++) total -= gap[i];
    cout << total << endl;
    return 0;
}