跳转至

贪心算法

例题

活动安排

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 一 基础算法 | 1 贪心算法
// #10000. 「一本通 1.1 例 1」活动安排
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<lli, lli> pii;
const int MAXn = 1e3 + 9;
vector<pii> d;

bool cmp(const pii & x, const pii & y) {
    if(x.second == y.second) return x.first < y.first;
    return x.second < y.second;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        lli ia, ib;
        scanf("%lld%lld", &ia, &ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmp);
    int ans = 0, last = -1;
    for(pii x : d)
        if(x.first >= last) ans ++, last = x.second;
    printf("%d", ans);
    return 0;
}

种树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 一 基础算法 | 1 贪心算法
// #10001. 「一本通 1.1 例 2」种树
// P1250 种树
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef tuple<lli, lli, lli> tup;
const int MAXn = 3e4 + 9;
vector<tup> d;
bool ped[MAXn];

bool cmp(const tup & x, const tup & y) {
    if(get<1>(x) == get<1>(y)) {
        if(get<0>(x) == get<0>(y)) return get<2>(x) > get<2>(y);
        return get<0>(x) < get<0>(y);
    }
    return get<1>(x) < get<1>(y);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        lli ia, ib, ic;
        scanf("%lld%lld%lld", &ia, &ib, &ic);
        d.push_back({ia, ib, ic});
    }
    sort(d.begin(), d.end(), cmp);
    int ans = 0;
    for(tup x : d) {
        int nped = 0, need = get<2>(x);
        for(int i = get<0>(x); i <= get<1>(x); i ++)
            if(ped[i]) {
                nped ++;
                if(nped >= need) break;
            }
        if(nped >= need) continue;
        int last = need - nped;
        for(int i = get<1>(x); i >= get<0>(x); i --)
            if(!ped[i]) {
                ped[i] = true;
                ans ++;
                last --;
                if(!last) break;
            }
    }
    printf("%d", ans);
    return 0;
}

喷水装置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 一 基础算法 | 1 贪心算法
// #10002. 「一本通 1.1 例 3」喷水装置
// UVA10382 Watering Grass
#include <bits/stdc++.h>
#define ld long double
using namespace std;
typedef pair<ld, ld> pdd;
vector<pdd> d;

bool cmp(const pdd & x, const pdd & y) {
    return x.first < y.first;
}

int main() {
    int T;
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _ ++) {
        d.clear();
        int n = 0, tms, l, w;
        scanf("%d%d%d", &tms, &l, &w);
        for(int i = 1, p, r; i <= tms; i ++) {
            scanf("%d%d", &p, &r);
            if(2 * r <= w) continue;
            ld ll = sqrt(r * r - w * w / (ld)4.0);
            d.push_back({p - ll, p + ll});
            n ++;
        }
        sort(d.begin(), d.end(), cmp);
        bool flg = false;
        int ans = 0, x = 0;
        ld p = 0;
        while(p < l) {
            ld fp = -1;
            for(; x < n && d[x].first <= p; x ++) {
                if(d[x].first <= p && p <= d[x].second)
                    fp = max(fp, d[x].second);
            }
            if(fp == -1) {
                flg = true;
                break;
            }
            ans ++;
            p = fp;
        }
        if(flg) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", ans);
    }
    return 0;
}

加工生产调度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 一 基础算法 | 1 贪心算法
// #10003. 「一本通 1.1 例 4」加工生产调度
// P1248 加工生产调度
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 1e3 + 9;
int d1[MAXn], d2[MAXn];
vector<int> n1, n2;

bool cmp1(const int & x, const int & y) {
    return d1[x] < d1[y];
}

bool cmp2(const int & x, const int & y) {
    return d2[x] > d2[y];
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d1[i]);
    for(int i = 1, ib; i <= n; i ++) {
        scanf("%d", &d2[i]);
        if(d1[i] < d2[i]) n1.push_back(i);
        else n2.push_back(i);
    }
    sort(n1.begin(), n1.end(), cmp1);
    sort(n2.begin(), n2.end(), cmp2);
    lli a = 0, b = 0;
    for(auto i : n1) {
        a += d1[i];
        if(b < a) b = a;
        b += d2[i];
    }
    for(auto i : n2) {
        a += d1[i];
        if(b < a) b = a;
        b += d2[i];
    }
    printf("%lld\n", max(a, b));
    for(auto i : n1) printf("%d ", i);
    for(int p = 0; p < n2.size() - 1; p ++) printf("%d ", n2[p]);
    printf("%d", n2[n2.size() - 1]);
    return 0;
}

智力大冲浪

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 一 基础算法 | 1 贪心算法
// #10004. 「一本通 1.1 例 5」智力大冲浪
// P1230 智力大冲浪
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 500 + 9;
bool ved[MAXn];
vector<pii> d;    // first: deadline; second: v

bool cmp(const pii & x, const pii & y) {
    if(x.second == y.second) return x.first > y.first;
    return x.second > y.second;
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    for(int i = 0, ia; i < n; i ++) {
        scanf("%d", &ia);
        d.push_back({ia, 0});
    }
    for(int i = 0; i < n; i ++) {
        scanf("%d", &d[i].second);
    }
    sort(d.begin(), d.end(), cmp);
    for(int i = 0; i < n; i ++) {
        int dl = d[i].first;
        bool can = false;
        for(int t = dl; t >= 1; t --)
            if(!ved[t]) {
                ved[t] = true;
                can = true;
                break;
            }
        if(!can) {
            m -= d[i].second;
        }
    }
    printf("%d", m);
    return 0;
}

练习题

数列极差

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 一 基础算法 | 1 贪心算法
// #10005. 「一本通 1.1 练习 1」数列极差
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 5e4 + 9;
int d[MAXn];
priority_queue<int> xgd;
priority_queue<int, vector<int>, greater<int> > dgd;

int main() {
    int n;
    scanf("%d", &n);
    if(n == 0) return 0 * printf("0");
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]),
        xgd.push(d[i]),
        dgd.push(d[i]);
    while(xgd.size() != 1) {
        int a = xgd.top(); xgd.pop();
        int b = xgd.top(); xgd.pop();
        xgd.push(a * b + 1);
        a = dgd.top(); dgd.pop();
        b = dgd.top(); dgd.pop();
        dgd.push(a * b + 1);
    }
    printf("%d", dgd.top() - xgd.top());
    return 0;
}

数列分段

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 一 基础算法 | 1 贪心算法
// #10006. 「一本通 1.1 练习 2」数列分段
// P1181 数列分段 Section I
#include <bits/stdc++.h>
#define lli long long int
using namespace std;

int main() {
    int n, mx;
    scanf("%d%d", &n, &mx);
    lli addi = 0, ans = 0;
    for(int i = 1, ia; i <= n; i ++) {
        scanf("%d", &ia);
        addi += ia;
        if(addi > mx) {
            addi = ia;
            ans ++;
        }
    }
    if(addi) ans ++;
    printf("%lld", ans);
    return 0;
}

线段

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 一 基础算法 | 1 贪心算法
// #10007. 「一本通 1.1 练习 3」线段
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> d;

bool cmp(const pii & x, const pii & y) {
    return x.second < y.second;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        if(ia > ib) swap(ia, ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmp);
    int last = -1, ans = 0;
    for(pii x : d) {
        if(x.first >= last) {
            last = x.second;
            ans ++;
        }
    }
    printf("%d", ans);
    return 0;
}

家庭作业

此类贪心题，不同方法分析，见 题目分享 / LOJ10008。

法 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 一 基础算法 | 1 贪心算法
// #10008. 「一本通 1.1 练习 4」家庭作业
// 100 AC 法1：枚举所有时间，并放入能放入的元素中奖励数最大的 [https://loj.ac/s/2134260]
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 1e6 + 9;
vector<int> d[MAXn];    // d[x]: 死线为 x 的所有奖励
priority_queue<int> pq;

int main() {
    int n, maxdl = 1;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d[ia].push_back(ib);
        maxdl = max(maxdl, ia);
    }
    lli ans = 0;
    for(int i = maxdl; i >= 1; i --) {
        for(int v : d[i]) pq.push(v);
        if(!pq.empty()) ans += pq.top(), pq.pop();
    }
    printf("%lld", ans);
    return 0;
}

法 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 一 基础算法 | 1 贪心算法
// #10008. 「一本通 1.1 练习 4」家庭作业
// 80 TLE 法2：按照奖励大小排序，优先安排奖励数最大的，且尽量靠后地安排 [https://loj.ac/s/2134292]
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 1e6 + 9;
bool ved[MAXn];
vector<pii> d;    // first: deadline; second: v

bool cmp(const pii & x, const pii & y) {
    if(x.second == y.second) return x.first > y.first;
    return x.second > y.second;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmp);
    lli ans = 0;
    for(pii x : d) {
        for(int i = x.first; i >= 1; i --)
            if(!ved[i]) {
                ved[i] = true;
                ans += x.second;
                break;
            }
    }
    printf("%lld", ans);
    return 0;
}

法 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 一 基础算法 | 1 贪心算法
// #10008. 「一本通 1.1 练习 4」家庭作业
// 100 AC 法3：使用反悔贪心：按照截止时间从小到大排序，如果放不下尝试替换放好的元素中奖励最小的 [https://loj.ac/s/2134430]
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 1e6 + 9;
const int MAXdl = 7e5 + 9;
priority_queue<pii, vector<pii>, greater<pii> > pq;    // first: v; second: time
vector<pii> d;    // first: deadline; second: v

bool cmp(const pii & x, const pii & y) {
    if(x.first == y.first) return x.second > y.second;
    return x.first < y.first;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia, ib; i <= n; i ++) {
        scanf("%d%d", &ia, &ib);
        d.push_back({ia, ib});
    }
    sort(d.begin(), d.end(), cmp);
    lli ans = 0;
    int t = 1;
    for(pii x : d) {
        if(x.first < t) {
            if(!pq.empty() && pq.top().first < x.second) {
                int tt = pq.top().second;
                ans -= pq.top().first;
                pq.pop();
                pq.push({x.second, tt});
                ans += x.second;
            }
            else continue;
        }
        else {
            pq.push({x.second, t});
            ans += x.second;
            t ++;
        }
    }
    printf("%lld", ans);
    return 0;
}

钓鱼

此题亦可用 dp 完成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 一 基础算法 | 1 贪心算法
// #10009. 「一本通 1.1 练习 5」钓鱼
// P1717 钓鱼
// 使用贪心的做法。此题亦可用 dp 完成
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<lli, int> pii;
const int MAXn = 25 + 9;
lli d[MAXn], adc[MAXn], js[MAXn];
priority_queue<pii> pq;

void pqclear() {
    while(!pq.empty()) pq.pop();
}

void pqini(int nd) {
    for(int i = 1; i <= nd; i ++)
        pq.push({d[i], i});
}

int main() {
    int n; lli h;
    scanf("%d%lld", &n, &h);
    h *= 12;
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &d[i]);
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &js[i]);
    for(int i = 1, c; i <= n - 1; i ++)
        scanf("%d", &c),
        adc[i] = adc[i - 1] + c;
    lli aans = 0;
    for(int nd = 1; nd <= n; nd ++) {
        lli nh = h - adc[nd - 1], ans = 0;
        if(nh <= 0) continue;
        pqclear(); pqini(nd);
        for(int t = 1; t <= nh && pq.top().first >= 0; t ++) {
            pii now = pq.top();
            pq.pop();
            if(now.first >= 0) {
                ans += now.first;
                now.first -= js[now.second];
                pq.push(now);
            }
        }
        aans = max(aans, ans);
    }
    printf("%lld", aans);
    return 0;
}

糖果传递

\(n\) 较小时，亦可用 网络流 完成，见 洛谷 P4016 负载平衡问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 一 基础算法 | 1 贪心算法
// #10010. 「一本通 1.1 练习 6」糖果传递
// P2512 [HAOI2008] 糖果传递
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 1e6 + 9;
lli a[MAXn];
vector<lli> v;

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, ia; i <= n; i ++) {
        scanf("%d", &ia);
        a[i] = a[i - 1] + ia;
    }
    lli avg = a[n] / n;
    for(int i = 1; i <= n; i ++)
        v.push_back(a[i - 1] - avg * (i - 1));
    sort(v.begin(), v.end());
    lli x1 = v[n / 2];
    lli ans = 0;
    for(lli p : v) ans += abs(x1 - p);
    printf("%lld", ans);
    return 0;
}