专题三 贪心、倍增

2025ACM寒假集训

专题三 贪心、倍增

102400226 石华波

Vjudge账号:DustLi

问题一 Priority Queue

问题陈述

优先队列是一种数据结构，它维护一组元素 SS，每个元素都有一个关联的值（键），并支持以下操作：

  • insert(S,k)insert(S,k)：将一个元素 kk 插入到集合 SS 中
  • extractMax(S)extractMax(S)：移除并返回具有最大键的 SS 元素

编写一个程序，对优先队列 SS 执行 insert(S,k)insert(S,k) 和 extractMax(S)extractMax(S) 操作。 优先队列管理一组整数，这些整数也是优先级的键。

输入

多个对优先队列 SS 的操作被给出。每个操作在一行中给出，格式为 “insert kk"、“extract” 或 “end”。这里，kk 表示要插入优先队列的整数元素。

输入以 “end” 操作结束。

输出

对于每个 “extract” 操作，打印从优先队列 SS 中提取的元素，每个元素占一行。

解题思路

优先队列，套版。

AC代码：

 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

#include<iostream>
#include<climits>
#include <queue>

#define ll long long

using namespace std;

int main() {
    priority_queue<int> pq;
    string s;
    cin>>s;
    while(s!="end") {
        if(s=="insert") {
            int x;
            cin>>x;
            pq.push(x);
        }
        else if(s=="extract") {
            cout<<pq.top()<<endl;
            pq.pop();
        }
        cin>>s;
    }
    return 0;
}

问题二 ST 表 && RMQ 问题

问题陈述

给定一个长度为 N的数列，和 M次询问，求出每一次询问的区间内数字的最大值。

解题思路

使用ST表，倍增地求出[i,i+2^j]区间中的最大值，输出时查表即可。

本题读入和输出处理比较重要，如若不对cout进行处理或更换必定超时，故更换为printf并使用快读。

AC代码：

 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

#include <cmath>
#include<iostream>

#define ll long long

using namespace std;

int ST[20][100001];
int LogTwo[100001];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int main() {
    int N,M;
    N=read();
    M=read();
    for (int i=1;i<=N;i++) LogTwo[i]=log2(i);
    for(int i=1;i<=N;i++) cin>>ST[0][i];
    int len=log2(N);
    for(int i=1;i<=len;i++) {
        for(int j=1;j<=N-(1<<i)+1;j++) {
            ST[i][j]=max(ST[i-1][j],ST[i-1][j+(1<<i-1)]);
        }
    }
    for(int i=1;i<=M;i++) {
        int l,r;
        l=read();
        r=read();
        len=LogTwo[r-l+1];
        printf("%d\n",max(ST[len][l],ST[len][r-(1<<len)+1]));
    }
    return 0;
}

问题三 合并果子

问题陈述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3种果子，数目依次为 1 ， 2 ， 9。可以先将 1、 2堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 3+12=15 。可以证明 15 为最小的体力耗费值。

解题思路

总共需要合并的次数是已知的，即x-1次合并可以使x堆果子合并为一堆。在固定合并次数的条件下，优先合并重量较小的堆会使总消耗最少。使用小根堆，每次合并堆顶的两个元素并删除，将新生成的元素加入堆中，直到堆中仅有一个元素。

AC代码：

 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

#include<iostream>
#include <queue>

#define ll long long

using namespace std;

priority_queue<int, vector<int>,greater<int> > pq;

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++) {
        int t;
        cin>>t;
        pq.push(t);
    }
    int sum=0;
    while(pq.size()>=2) {
        int a=pq.top();
        pq.pop();
        int b=pq.top();
        pq.pop();
        pq.push(a+b);
        sum+=a+b;
    }
    cout<<sum;
    return 0;
}

问题4 约瑟夫问题

问题陈述

n 个人围成一圈，从第一个人开始报数,数到 m的人出列，再由下一个人重新从 1开始报数，数到 m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

解题思路

使用队列对游戏进行模拟，每次报数增加都令此时的队首移动至队尾，当报至M时，此时的队首出列，重置计数器。

AC代码：

 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

#include<iostream>
#include <queue>

#define ll long long

using namespace std;

queue<int> q;

int main() {
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=N;i++) q.push(i);
    int cnt=0;
    while(!q.empty()) {
        cnt++;
        if(cnt==M) {
            cout<<q.front()<<" ";
            q.pop();
            cnt=0;
        }
        else {
            int front=q.front();
            q.pop();
            q.push(front);
        }
    }
    return 0;
}

问题五 Look Up S

问题陈述

约翰的 N(1≤N≤105)头奶牛站成一排，奶牛 i的身高是 Hi(1≤Hi≤106)。现在，每只奶牛都在向右看齐。对于奶牛 i，如果奶牛 j满足 i<j且 Hi<Hj，我们可以说奶牛 i可以仰望奶牛 j。 求出每只奶牛离她最近的仰望对象。

解题思路

使用单调栈，栈中存储奶牛序号。优先处理最右端奶牛，因为其必定没有仰望对象，使其入栈。从右向左遍历奶牛，对于每一次遍历，令身高小于此奶牛的编号出栈，若栈中仍有元素，则栈顶为其仰望对象，若栈中没有元素，则其没有仰望对象，记为0。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<iostream>
#include <stack>

#define ll long long

using namespace std;

stack<int> s;

int H[100001],F[100001];

int main() {
    int N;
    cin>>N;
    for(int i=1;i<=N;i++) cin>>H[i];
    for(int i=N;i>=1;i--) {
        while(!s.empty()&&H[s.top()]<=H[i]) s.pop();
        if(s.empty()) F[i]=0;
        else F[i]=s.top();
        s.push(i);
    }
    for(int i=1;i<=N;i++) cout<<F[i]<<endl;
    return 0;
}

问题六 国旗计划

A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了 N名优秀的边防战士作为这项计划的候选人。

A 国幅员辽阔，边境线上设有 M个边防站，顺时针编号 1至 M。每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。N名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。

现在，国土安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划。不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。

解题思路

每位战士都不被包含，则以左端点排序，对于一个战士，其右端点左侧最近的左端点对应的战士即为能使参与人数最少的战士。

以倍增的思路，找出每位战士下2^i个能使参与人数最少的战士，转移方程： ST[i][j]=ST[i-1][ST[i-1][j]]

注意排序后战士编号为乱序，需存储战士读入时的编号。

AC代码：

 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
53
54
55
56
57
58
59
60

#include <algorithm>
#include<iostream>
#include <bits/ranges_algo.h>

#define ll long long

using namespace std;

typedef struct{
    int No;
    int L;
    int R;
}Solider;

const int maxN=200005;
int ST[20][maxN<<1];
int Ans[maxN];
Solider Sol[maxN<<1];

int Cmp(Solider a,Solider b) {
    return a.L<b.L;
}

int main() {
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=N;i++) {
        cin>>Sol[i].L>>Sol[i].R;
        Sol[i].No=i;
        Sol[i].R=Sol[i].L>Sol[i].R?Sol[i].R+M:Sol[i].R;
    }
    sort(Sol+1,Sol+N+1,Cmp);
    for(int i=1;i<=N;i++) {
        Sol[i+N].L=Sol[i].L+M;
        Sol[i+N].R=Sol[i].R+M;
    }
    for(int i=1,j=1;i<=N<<1;i++) {
        while(j<=N<<1&&Sol[i].R>=Sol[j].L) j++;
        ST[0][i]=j-1;
    }
    for(int i=1;i<20;i++) {
        for(int j=1;j<=N<<1;j++) {
            ST[i][j]=ST[i-1][ST[i-1][j]];
        }
    }
    for(int i=1;i<=N;i++) {
        int ansi=0,p=i;
        for(int j=19;j>=0;j--) {
            if(ST[j][p]&&Sol[ST[j][p]].R<Sol[i].L+M) {
                ansi+=1<<j;
                p=ST[j][p];
            }
        }
        Ans[Sol[i].No]=ansi+2;
    }
    for(int i=1;i<=N;i++) {
        cout<<Ans[i]<<" ";
    }
    return 0;
}

学习总结

本专题内容主要为贪心与倍增，通过学习，提高了自己的能力。

Licensed under CC BY-NC-SA 4.0
© 2025 - 2026 Dust_Li
2025寒假ACM新生线上集训
使用 Hugo 构建
主题 Stack 由 Jimmy 设计