YbtOJ「基础算法」第2章 贪心算法

YbtOJ大全

【例题1】奶牛晒衣服

一道很基础的贪心，用大根堆维护当前状态下衣服湿度的最大值，然后让它减去 $b$，同时维护一个时间戳 $t$，判断 $q.top()-t\times a>0$ 是否成立即可。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
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<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
priority_queue<int> q;
const int M = 5e5 + 10;
int n,a,b,x,t;
signed main(){
    n = read(),a = read(),b = read();
    rep(i,1,n) x = read(),q.push(x);
    while(q.top() - t*a > 0){
        int u = q.top();
        q.pop();
        u -= b;
        q.push(u);
        t++;
    }
    printf("%d\n",t);
    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

【例题2】雷达装置

一开始的思路是按左端点从小到大排序，然后记录下来当前的最大位置 $pos$，每进入一个 $a[i].r$ 就和 $pos$ 比较，如果小就不管，大就更新。但如果有重叠的部分，只记录右端点，如果有两个小段，一个在中间，一个跨过了右端点，会让答案变小。

正确的贪心是按右端点升序排序，同样记录右端点 $pos$，如果当前进入的 $a[i].l$ 和 $a[i].r$ 的区间包含 $pos$，可以不管，否则记录能到的最大右端点。

#include 
#include 
#include 
#include 
#include 
#define re register
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
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<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
const int M = 1e5+10;
int n;
double d;
struct node{
    double l,r;
    friend bool operator < (node a,node b) { return a.r < b.r; }
}a[M];
signed main(){
    n = read();
    scanf("%lf",&d);
    rep(i,1,n){
        double x,y;
        scanf("%lf%lf",&x,&y);
        if(y > d) { printf("-1\n"); return 0; }
        a[i].l = 1.0 * (1.0 * x - 1.0 * sqrt(d*d - y*y));
        a[i].r = 1.0 * (1.0 * x + 1.0 * sqrt(d*d - y*y));
    }
    sort(a+1,a+n+1);
    int ans = 1;
    double you = a[1].r;
    rep(i,2,n){
        if(a[i].l <= you && you <= a[i].r) continue;
        ans++;
        you = a[i].r;
    }
    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

【例题3】畜栏预定

需要维护一个小根堆，存当前牛所在牛栏的编号和时间的右端点。每一次进来一头牛，把它的左端点和 $q.top().r$ 比较，如果比这个小，就需要新建一个畜栏，否则可以用这个畜栏。

注意，一开始对于原数组的排序，需要按右端点从小到大排序，这样才能保证结束的时间递增。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
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<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
typedef pair<int,int> pii;
const int M = 1e5+10;
struct node{
    int l,r,id;
    friend bool operator < (node a,node b) { return a.l < b.l; }
}a[M];
int n,cnt = 1,ans = 1;
struct qwq{
    int id,rht;
    friend bool operator > (qwq a,qwq b) { return a.rht > b.rht; }
};
priority_queue<qwq,vector<qwq>,greater<qwq> > q;
signed main(){
    n = read();
    rep(i,1,n) scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1);
    a[1].id = 1;
    q.push(qwq{1,a[1].r});
    rep(i,2,n){
        if(a[i].l > q.top().rht){
            a[i].id = q.top().id;
            q.pop();
            q.push(qwq{a[i].id,a[i].r});
        }
        else{
            cnt++;
            ans = max(ans,cnt);
            a[i].id = cnt;
            q.push(qwq{a[i].id,a[i].r});
        }
    }
    printf("%d\n",ans);
    rep(i,1,n) printf("%d\n",a[i].id);
    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

【例题4】荷马史诗

哈夫曼树的题。哈夫曼树是带权路径长度 $WPL$ 最短的多叉树 $($ 最优多叉树 $)$。以二叉树为例，给 $n$ 个点，每个点都有权值，构造一棵哈夫曼树。构造过程是每次选剩下的两棵根权值最小的树合并成一棵新树，新树的根权值等于两棵合并前树的根权值和 $($ 一开始一个点也看成一棵树，只不过这棵树没有孩子节点 $)$。

这道题是一个 $k$ 叉树。如果是二叉树，不会存在最后不是两个节点合并的情况。但 $k$ 叉树可能存在。所以我们要在第一层补 $0$。如果 $(n-1)/(k-1)\ne 0$，就说明需要补点，需要补 $k-1-(n-1)/(k-1)$ 个点。

我们构造一个小根堆，存当前点的值和高度。每一次取堆顶的 $k$ 个元素，将他们的值加起来，同时高度 $h+1$，并把新点假如小根堆中，依次循环到最后只剩一个点为止。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long 
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e5+10;
int a[M];
struct node{
	int w,h;
	friend bool operator < (node a,node b){
		if(a.w == b.w) return a.h > b.h;
		return a.w > b.w;
	}
};
priority_queue<node> q;
int n,k;
int ans,cnt;
signed main(){
	n = read(),k = read();
	rep(i,1,n){
		a[i] = read();
		q.push(node{a[i],1});
	}
	if((n-1)%(k-1) != 0) cnt = k - 1 - (n-1)%(k-1);
	rep(i,1,cnt) q.push(node{0,1});
	while(q.size() >= k){
		int h = 0,w = 0;
		rep(i,1,k){
			auto u = q.top();
			q.pop();
			h = max(h,u.h);
			w += u.w;
		}
		ans += w;
		q.push(node{w,h+1});
	}
	printf("%lld %lld\n",ans,q.top().h-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
43
44
45
46
47
48
49
50
51
52

$1.$ 排队接水

按时间从小到大贪心即可。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
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<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
struct date{
	int id , time ;
	friend bool operator < (date a , date b ){
		return a.time < b.time;
	}
} vec[1010];
int main(){
	int n;
	double tot=0,sum=0;
	cin >> n;
	for(int i=1 ; i<=n ; i++){
		cin >> vec[i].time;
		vec[i].id = i;
	}
	sort(vec+1,vec+n+1);
	for(int i=1 ; i<=n ; i++){
		tot += sum ;
		sum += vec[i].time;
	}
	for(int i=1 ; i<=n ; i++){
		cout << vec[i].id << " ";
	}
	cout << endl;
	cout << fixed << setprecision(2) << tot/n;
	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

$2.$ 砍树问题

每一棵树只跟左面相邻和右面相邻的两棵树有关，算满足条件的值即可。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 2e5+10;
struct node{
	int pos,h;
	friend bool operator < (node a,node b) { return a.pos < b.pos; }
}a[M];
int n;
signed main(){	
	n = read();
	rep(i,1,n) scanf("%d%d",&a[i].pos,&a[i].h);
	sort(a+1,a+n+1);
	int ans = 0;
	rep(i,1,n){
		if(i == 1) ans += max(0,a[i].h-(a[i+1].pos-a[i].pos));
		else if(i == n) ans += max(0,a[i].h-(a[i].pos-a[i-1].pos));
		else ans += max(0,max(a[i].h-(a[i].pos-a[i-1].pos),a[i].h-(a[i+1].pos-a[i].pos)));
	}
	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

$3.$ 出栈序列

首先，我们对于原序列维护一个后缀最大值。对于 $a[i]$，先将其入栈，然后从栈顶开始依次比较栈顶元素和从 $i+1$ 到 $n$ 的最大值，如果比后面的最大值大，就将栈顶元素弹出，否则继续循环即可。最后在栈不为空的时候，依次弹出栈顶。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e6+10;
stack<int> s;
int a[M],hou[M];
int n;
signed main(){
	n = read();
	rep(i,1,n) a[i] = read();
	drep(i,n,1) hou[i] = max(hou[i+1],a[i]);
	rep(i,1,n){
		s.push(a[i]);
		while(!s.empty() && s.top() > hou[i+1]) printf("%d ",s.top()),s.pop();
	}
	while(!s.empty()) printf("%d ",s.top()),s.pop();
	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

$4.$ 序列问题

第一问求或的最大值，显然把每一个 $a[i]$ 或起来即可。

第二问求与的最大值。对于两个数 $a$，$b$，它们与的值一定会小于等于 $a$ 和 $b$ 的值。所以长度正好为 $k$ 即为最大值。

由于 $a[i]\le 2^{31}-1$ ，我们可以枚举它的每一位是否是 $1$，同时我们对于每一个 $i(0\le i\le 31)$，维护一个前缀和数组 $sum[i][j]$ 表示 $i$ 这一位，前 $j$ 个有多少个 $1$。最后统计答案的时候对于对于每一个长度为 $k$ 的区间，如果 $i$ 这一位正好有 $k$ 个 $1$，就把 $res|=(1<<i)$，答案即为对于每一个 $res$， $ans=\max (ans,res)$。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e6+10;
int a[M],sum[35][M],tot[M];
int n,k; 
int ans1,ans2;
signed main(){
	n = read(),k = read();
	rep(i,1,n) a[i] = read(),ans1 |= a[i];
	rep(i,1,n) rep(j,0,31) sum[j][i] = sum[j][i-1] + (((1<<j) & a[i]) == 0 ? 0 : 1);
	rep(i,1,n-k+1){
		int res = 0;
		rep(j,0,31) tot[j] = sum[j][i+k-1] - sum[j][i-1];
		rep(j,0,31) if(tot[j] == k) res |= (1<<j);
		ans2 = max(ans2,res);
	}
	printf("%d %d\n",ans1,ans2);
	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

$5.$ 仙人之环

可以算是一道好题吧。首先对于不在环上的点，我们每删一条边就能多一个联通块，所以我们要先把这些点连的边删掉。

然后就是如何删环。先预处理出每一个环的大小，按从大到小排序，如果删去环上的一条边，问题就转化为了一条链，每次删一条边就会多一个联通块。

#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
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<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
const int M = 4e6+10;
int head[M],dfn[M],siz[M],dep[M],s[M];
int n,m,k;
int cnt,dfncnt,num,ans,tot;
struct edge{
    int to,nxt;
}e[M];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
inline void dfs(int u,int fa){
    dep[u] = dep[fa]+1;
    for(re int i(head[u]) ; i ; i=e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        if(!dep[v]) dfs(v,u);
        else if(dep[v] < dep[u]){
            if(dep[u] - dep[v] > 1){
                s[++tot] = dep[u]-dep[v]+1;
                num += dep[u]-dep[v]+1;
            }
        }
    }
}
signed main(){
    n=read(),m=read(),k=read();
    rep(i,1,m){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    rep(i,1,n){
        if(!dep[i]){
            dfs(i,0);
            ans++;
        }
    }
    if(k <= m-num){
        printf("%lld\n",k + ans);
        return 0;
    }
    sort(s+1,s+tot+1);
    k -= m-num;
    ans += m-num;
    for(re int i(tot) ; i ; --i){
        if(k >= s[i]){
            k -= s[i];
            ans += s[i]-1;
        }
        else{
            ans += k-1;
            printf("%lld\n",ans);
            return 0;
        }
    }
    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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74