AcWing 第6讲 贪心算法

区间问题

区间选点

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;

struct struct_edge {
    int l, r;
}edge[N];

bool cmp(struct_edge a, struct_edge b) {
    return a.r < b.r;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) cin >> edge[i].l >> edge[i].r;

    sort(edge, edge + n, cmp);

    // for (int i = 0;i < n;i++) cout << edge[i].l << " " << edge[i].r << endl;
    int ans = 1, right = edge[0].r;
    for (int i = 1;i < n;i++) {
        if (edge[i].l > right) {
            ans++;
            right = edge[i].r;
        }
    }
    cout << ans;

    return 0;
}

区间分组

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
int num[2 * N], idx;

// 一个活动开始时，分配一间教室，一个活动结束时，释放一间教室，这样所需的教室数量上下浮动
// 而浮动过程中的最大值就是所需教室数量的最小值
// 没结束就不释放，结束了就把对应的教室释放，不用管释放的是哪一间教室

int main() {
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int a, b;
        cin >> a >> b;
        num[idx++] = 2 * a;
        num[idx++] = 2 * b + 1;
    }

    sort(num, num + idx);

    int cnt = 0, ans = 0;
    for (int i = 0;i < idx;i++) {
        if (num[i] % 2 == 0)cnt++;
        else cnt--;
        ans = max(ans, cnt);
    }

    cout << ans;

    return 0;
}

区间覆盖

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
struct struct_edge {
    int l, r;
}edge[N];

bool cmp(struct_edge a, struct_edge b) {
    return a.r < b.r;
}

int main() {
    int right, left, n;
    cin>>right>>left;

    for (int i = 0;i < n;i++) cin >> edge[i].l >> edge[i].r;

    sort(edge, edge + n, cmp);

    for (int i = 0;i < n;i++) {
        if (edge[i].r <= left || edge[i].l > left) continue;
        
        
    }

    return 0;
}

哈夫曼树（合并果子）

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;

const int N = 100010;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0;i < n;i++) {
        int a;
        cin >> a;
        heap.push(a);
    }

    LL ans = 0;
    while (heap.size()>1) {
        int first = heap.top();
        heap.pop();
        int second = heap.top();
        heap.pop();
        first += second;
        heap.push(first);
        ans+=first;
    }
    cout << ans;


    return 0;
}

排序不等式（排队打水）

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
LL n, num[N];

int main() {
    cin >> n;
    for (int i = 2;i <= n + 1;i++) cin >> num[i];

    sort(num, num + n + 2);
    // for (int i = 1;i <= n;i++) cout<<num[i]<<" ";
    LL ans = 0;
    for (int i = 1;i <= n;i++) {
        num[i] += num[i - 1];
        ans += num[i];
    }
    // for (int i = 1;i <= n;i++) cout<<num[i]<<" ";

    cout << ans;

    return 0;
}

绝对值不等式（货仓选址）

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
// 把A[l]~A[N] 排序，设货仓建在X 坐标处，X 左侧的商店有P 家，右侧的商店有Q 家。
// 若p < Q, 则每把货仓的选址向右移动1 单位距离，距离之和就会变小。
// 同理，若p > Q, 则货仓的选址向左移动会使距离之和变小。
// 当P = Q 时为最优解。
// 只要货仓建在PQ之间，距离之和就是恒定的
int main() {
    int n;
    cin >> n;
    int num[N];
    for (int i = 0;i < n;i++) cin >> num[i];

    sort(num, num + n);

    LL ans = 0;
    for (int i = 0;i < n;i++) ans += abs(num[i] - num[n / 2]);
    cout << ans;

    return 0;
}

推公式（耍杂技的牛）

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
typedef pair<int, int> PII;
PII cow[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int a, b;
        cin >> a >> b;
        cow[i] = { a + b,b };
    }
    sort(cow, cow + n);

    LL ans = -1e18, fee=0;
    for (int i = 0;i < n;i++) {
        fee -= cow[i].second;
        ans = max(ans, fee);
        fee += cow[i].first;
    }

    cout << ans;

    return 0;
}