ACM贪心基础

一、区间选点（区间问题）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }

    printf("%d\n", res);

    return 0;
}

二、最大不相交区间数量（区间问题）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N  = 100010;
//保存区间
vector<vector<int>> a(N,vector<int>(2,0));
int n;

int main()
{
    cin >> n;
    //读入区间
    for(int i = 0; i< n; i++)
    {
        int l, r;
        cin >> l >> r;
        a[i][0] = l;
        a[i][1] = r;
    }
    // 按右端点排序
    sort(a.begin(), a.begin() + n, [](vector<int> &a, vector<int> &b){return a[1] < b[1];});
    // res 保存答案，end 最后一个选中区间的右端点
    int res = 0, end = -1e9 - 10;
    // 遍历区间
    for(int i = 0; i < n; i++)
    {
        // 如果当前当前区间和最后一个选中区间有重合，则跳过
        if(end >= a[i][0] && end <= a[i][1]) 
            continue;
        else
        {
            // 选中区间数量+1, 更右端点
            res++;
            end = a[i][1];
        }
    }
    cout << res;
    return 0;
}

三、区间分组（区间问题）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100100;

int n;
int b[2 * N], idx;

int main()
{
    scanf ("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数。
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数。
    }

    sort(b, b + idx);

    int res = 1, t = 0;
    for(int i = 0; i < idx; i ++)
    {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}

四、区间覆盖（区间问题）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++ ;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res ++ ;
        if (r >= ed)
        {
            success = true;
            break;
        }

        st = r;
        i = j - 1; 
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}

五、合并果子（Huffman树）

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }

    printf("%d\n", res);
    return 0;
}

六、排队打水（排序不等式）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;

int n;
int a[N];

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

    LL res = 0, t=0;
    for (int i = 0; i < n; i ++ ){
        res += t;
        t += a[i];
    }
    cout<<res<<endl;

    return 0;
}

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

八、耍杂技的牛（推公式）

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 5;
PII a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        a[i].first = x + y;
        a[i].second = y;
    }
    sort(a, a + n);
    ll res = -1e18, sum = 0;
    for(int i = 0; i < n; i ++ )
    {
        sum -= a[i].second;
        res = max(res, sum);
        sum += a[i].first;
    }
    cout << res << endl;
    return 0;
}