贪心

区间选点

1. 题目

1. 解法思路

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
struct Range{
    int l,r;
    bool operator < (const Range &w)const
    {
        return r < w.r;
    }
}range[N];

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

    return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
struct Range{
    int l,r;
}range[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        int l,r;
        cin >> l >> r;
        range[i] = {l,r};
    }
    sort(range,range + n ,[](const Range& u, const Range& v) {
            return u.r < v.r;
        });
    int res = 0,ed = -2e9;
    for(int i = 0;i <n;i++)
    {
        if(range[i].l > ed)
        {
            res++;
            ed = range[i].r;
        }
    }
    cout << res;

    return 0;
}

区间分组

题解

1. 小根堆维护所有组右端点最大值
2. 如果所有组右端点最小值（top）> l[i].l 不存在这个组 加新的组（push l[i].r）
3. 否则放入最小的组 （pop push）

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
struct Range{
    int l,r;
    bool operator < (const Range &W) const
    {
        return l < W.l;
    }
}range[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        int l,r;
        cin >> l >> r;
        range[i] = {l,r};
    }
    sort(range , range + n);
    priority_queue<int,vector<int>,greater<int> > heap;
    for(int i = 0; i < n;i ++)
    {
        auto r = range[i];
        if(heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else
        {
            heap.pop();
            heap.push(r.r);
        }
    }
    printf("%d", heap.size());
    return 0;
}

区间覆盖

题解

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

using namespace std;

const int N = 100010;

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

int main()
{
    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 flag = 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)
        {
            flag = true;
            break;
        }
        st = r;
        i = j - 1;
    }
    if(!flag) res = -1;
    cout << res << endl;


    return 0;
}

合并果子

题解

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

int n;
using namespace std;

int main(){
    cin >> n;
    priority_queue<int, vector<int>,greater<int>> heap;

    while(n--)
    {
        int x;
        cin >> 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);
    }
    cout << res << endl;
    return 0;
}

排队打水

题解

#include <iostream>
#include <algorithm>

typedef long long LL;
using namespace std;
const int N = 1e5 + 10;

int a[N];


int main(){
    LL res;
    int n;
    cin >> n;
    for(int i =0; i < n; i++)   cin >> a[i];
    sort(a, a + n);
    for(int i = 0; i < n; i++)
        res += a[i] * (n - i -1);
    cout << res << endl;

    return 0;
}

中位数

题解

#include <iostream>
#include <algorithm>


using namespace std;
const int N = 1e5 + 10;
int a[N];

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

    sort(a, a + n);
    int res = 0;
    for(int i =0; i < n; i++) res += abs(a[i] - a[n / 2]);

    cout << res << endl;

    return 0;
}

推公式

#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;

PII cow[N];

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

    int sum = 0,res = -2e9;
    for(int i = 0; i < n; i++)
    {
        int w = cow[i].second,s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res << endl;

    return 0;
}

生产调度

加工

• https://www.acwing.com/problem/content/description/4173/

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <math.h>
// #define int long long

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

struct Node {
	int a, b, pos;
    bool operator <(const Node &M)const{
        if((a<b && M.a<M.b) || (a==b && M.a==M.b) || (a>b && M.a>M.b))
        {
            if(a<=b) return a < M.a;
            else return b > M.b;
        }
        else return a-b < M.a-M.b;
    }
};
Node c[1010];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> c[i].a;
	for(int i = 1; i <= n; i ++) cin >> c[i].b, c[i].pos = i;
	sort(c + 1, c + n + 1);



	int f1 = 0, f2 = 0;
	for(int i = 1; i <= n; i ++)
	{
		f1 += c[i].a;
		f2 = max(f1, f2) + c[i].b;
	}
	cout << f2 << endl;
	for(int i = 1; i <= n; i ++) cout << c[i].pos << ' ';
	return 0;
}