YBTOJ 贪心算法合集

qwq

奶牛晒衣服

贪心，优先选湿度最大的烘干（注意烘干的衣服在单位时间内失去的水分为 $a+b$ ）

雷达装置

无解情况：$|y|>d$

由于 $d$ 确定，那么可以预处理出使每一个点 $i$ 能被扫到的位置范围 $[l,r]$，问题转化为求最少点数使得每条线段上都有点。

考虑对每条线段按 $r$ 升序排序，每次选择当前 $r$ 放雷达，一直向后找直到第一条当前点不能覆盖的线段，选取这条线段的 $r$ 点继续更新答案。

畜栏预定

也是区间问题，将区间按左端点升序排序，用优先队列维护当前在吃草的牛吃完草的先后顺序，那么每次贪心地选最早吃完的，继承它的畜栏，若无法选择再新开畜栏，必定最优。

不要忘了沿途记录畜栏个数的最大值qwq

#include
#define ll long long
#define ff(i,s,e) for(int i(s);i<=(e);++i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){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 N=5e4+5,M=1e6+5;
int n;
struct qwq{
    int l,r,id;
    bool operator < (const qwq &b) const{
        return r>b.r;
    }
}a[N];
int res[N];
priority_queue<qwq> q;
inline bool cmp(qwq x,qwq y){return x.l<y.l;}
signed main(){
    n=read();
    int ans=0;
    ff(i,1,n){
        a[i].l=read(),a[i].r=read(),a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    ff(i,1,n){
        if(q.empty()||q.top().r>=a[i].l) res[a[i].id]=q.size()+1;
        else res[a[i].id]=res[q.top().id],q.pop();
        q.push(a[i]);
        ans=max(ans,(int)q.size()); 
    }
    printf("%d\n",ans);
    ff(i,1,n) printf("%d\n",res[i]);
    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

荷马史诗

哈夫曼树模板而我并不会哈夫曼树

带权路径长度：树中所有叶节点权值乘其到根的路径长度之和。

哈夫曼树：带权路径长度最短的二叉树。

哈夫曼算法：贪心地使权值最大的点离根最近。

1. 将每个权值分别看作一棵树， $n$ 个权值看作一片森林。
2. 每次从森林里选两个根节点权值最小的树合并，新树根权值为原来两个根的权值之和。
3. 删去上一步选择的两棵树
4. 重复23步直到只剩一棵树。

哈夫曼编码：哈夫曼树上非叶结点连向左子节点的边权为0，连向右子节点的边权为1，从根节点到叶节点读取边权，即为该叶节点的哈夫曼编码。

本题为k叉哈夫曼树，注意补若干点权为0的结点，使哈夫曼树成为一课满k叉树，即 $(n-1)mod(k-1)=0$ （每次将 $k$ 个结点合并为一个，减少 $k-1$ 个顶点，一共要将 $n$ 个顶点合并为一个，减少 $n-1$ 个顶点）

code：

#include
#define int long long
#define ff(i,s,e) for(int i(s);i<=(e);++i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){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 N=1e5+5;
int n,k,w[N];
typedef pair<int,int> pir;//w,h
priority_queue<pir,vector<pir>,greater<pir> > q;
signed main(){
    n=read(),k=read();
    ff(i,1,n) w[i]=read(),q.push(make_pair(w[i],1));
    while((q.size()-1)%(k-1)!=0) q.push(make_pair(0,1));//补0 
    int ans=0;
    while(q.size()>=k){
        int h=-1,w=0;
        ff(i,1,k){//合并k个结点 
            pir qwq=q.top();
            q.pop();
            h=max(h,qwq.second),w+=qwq.first;
        }
        ans+=w;
        q.push(make_pair(w,h+1));
    }
    printf("%lld\n%lld\n",ans,q.top().second-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

排队接水

接水时间越长的人越往后，等ta的人越少，对平均等待时间的贡献越小。

砍树问题

（委实不知道这跟贪心有什么关系/kk

夹角不大于四十五度，抽象一点理解，即向左向右放倒每一棵树，都不会碰到别的树。

树的位置不能变，则每棵树高度最高为 $min(disl,disr)$，所以要从左到右按位置排个序，然后就做完了。

出栈序列

还是栈的两种操作中选择：push和pop

对于每一次，贪心地选择剩余未入栈序列元素最大值和栈顶元素的最大值，若栈顶元素更大，直接pop，否则后序元素依次入栈直到最大值加入，再将最大值出栈（没有重复元素就太良心了

所以维护后缀最大值即可。

序列问题

对于或运算，多或上一个元素只可能让当前二进制位为0的位置变成1，换言之，肯定不会比不或小，所以直接选择所有元素即可。

对于与运算，多与上一个元素只可能让当前二进制位为1的位置变成0，换言之，肯定不会比不与大，所以只选 $k$ 个元素一定最优。那么问题变成了如何快速求连续k个元素按位与的值。考虑位运算中的常用技巧：二进制拆分，对于每一位维护1的个数的前缀和，即可快速求出按位与后每一位的值。

code：

#include 
#define ll long long
#define ff(i,s,e) for(int i(s);i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){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 N=1e6+5,M=34;
int n,k,a[N];
int sum[N][M];
int now[M];
signed main(){
    n=read(),k=read();
    int ans1=0,ans2=0;
    ff(i,1,n){
        a[i]=read();
        ans1|=a[i];
        ff(j,0,31){
            if(a[i]&(1<<j)) sum[i][j]=sum[i-1][j]+1;
            else sum[i][j]=sum[i-1][j];
        }
    }
    ff(i,1,n-k+1){
        int l=i-1,r=i+k-1,res=0;
        ff(j,0,31) now[j]=sum[r][j]-sum[l][j];
        ff(j,0,31) if(now[j]==k) res|=(1<<j);
        ans2=max(ans2,res);
    }
    printf("%d %d",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
34
35

仙人之环

自己会贪心而不会求环不会求割边……

贪心思路：求出图中每条割边和每个环，断开割边一定使连通块数++，所以优先断开全部割边。而断开每个环，步数损失在于需要先多用一步断环为链，为使损失最小，考虑将环按节点数从大到小排序，依次断开，直至 $k$ 为0。

后来借鉴了这篇博客才学会了用tarjan求环和割边qwq

#include
#define ll long long
#define ff(i,s,e) for(int i(s);i<=(e);++i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){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 N=1e6+5;
int n,m,k;
int head[N],cnt;
struct qwq{
    int u,v,nxt;
}e[N<<2];
inline void add(int u,int v){
    e[++cnt]=qwq{u,v,head[u]},head[u]=cnt;
}
int dfn[N],low[N],tot,huan;
stack<int> s;
int siz[N];
int ans;
inline void tarjan(int x){
    dfn[x]=low[x]=++tot,s.push(x);
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]){ 
				if(s.top()==v){//(x,v)是割边 
					if(k) --k,++ans;
					s.pop();
				}
				else{//否则有一个环 
					++huan;
					while(!s.empty()){
						int u=s.top();
						s.pop();
						++siz[huan];
						if(u==v) break;
					}
				}
			}
        }
        else low[x]=min(low[x],dfn[v]);
    }
}
inline bool cmp(int x,int y){return x>y;}
signed main(){
    n=read(),m=read(),k=read();
    ff(i,1,m){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    ff(i,1,n) if(!dfn[i]) ++ans,tarjan(i);
    sort(siz+1,siz+huan+1,cmp);
    ff(i,1,huan){
		if(!k) break;
		--k;
		if(k>siz[i]) k-=siz[i],ans+=siz[i];
		else{ans+=k;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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68