首页 / 算法 / 【贪心】 BZOJ 3252:攻略
【贪心】 BZOJ 3252:攻略
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【贪心】 BZOJ 3252:攻略，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3456字，纯文字阅读大概需要5分钟。
内容图文
3252: 攻略
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 261 Solved: 90
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4 3 2 1 1
1 2
1 5
2 3
2 4
Sample Output
HINT
对于100%的数据，n<=200000，1<=场景价值<=2^31-1
很容易知道贪心策略:每次选价值最高的叶子节点
但是貌似很难搞的样子
朴素算法应该是n^2的样子。。
O（n）显然不太好搞。。
所以大约优化完后是O（nlgn）左右的复杂度。。
有两种logn的方法
1.黄学长的堆。。自行百度。。我只能说代码完全看不懂。。
2.DFS序+线段树
DFS处理出一个点管辖的所有点的DFS序。
然后线段树添加，每次删除。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<algorithm>
5 #include<vector>
6 7#define maxn 200001
8 9usingnamespace std;
10 11 vector<int>graph[maxn];
12 13int rev[maxn],in[maxn],father[maxn],dfn[maxn],last[maxn],tot=0;
14 15longlong a[maxn];
16 17bool vis[maxn];
18 19struct tr{
20int l,r,ps;
21longlong num,tag;
22 }tree[maxn*6];
23 24longlong read()
25{
26longlong x=0;char ch=getchar();
27while(ch<‘0‘||ch>‘9‘)ch=getchar();
28while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
29return x;
30}
31 32void DFS(int poi)
33{
34 dfn[poi]=++tot;
35 rev[tot]=poi;
36for(int i=graph[poi].size()-1;i>=0;i--)
37 {
38int u=graph[poi][i];
39 DFS(u);
40 }
41 last[poi]=tot;
42}
43 44void psh(int poi)
45{
46if(tree[poi].tag&&tree[poi].l!=tree[poi].r)
47 {
48 tree[poi<<1].tag+=tree[poi].tag;
49 tree[(poi<<1)|1].tag+=tree[poi].tag;
50 tree[poi<<1].num+=tree[poi].tag;
51 tree[(poi<<1)|1].num+=tree[poi].tag;
52 tree[poi].tag=0;
53 }
54}
55 56void update(int num,int l,int r,longlong d)
57{
58 psh(num);
59if(tree[num].l==l&&tree[num].r==r)
60 {
61 tree[num].num+=d;
62 tree[num].tag+=d;
63return;
64 }
65int mid=(tree[num].l+tree[num].r)>>1;
66if(mid>=r)update(num<<1,l,r,d);
67elseif(l>mid)update((num<<1)|1,l,r,d);
68else update(num<<1,l,mid,d),update((num<<1)|1,mid+1,r,d);
69if(tree[num].l==tree[num].r)return;
70if(tree[num<<1].num>tree[(num<<1)|1].num){tree[num].num=tree[num<<1].num,tree[num].ps=tree[num<<1].ps;}
71if(tree[(num<<1)|1].num>=tree[num<<1].num){tree[num].num=tree[(num<<1)|1].num,tree[num].ps=tree[(num<<1)|1].ps;}
72}
73 74void build(int num,int l,int r)
75{
76if(l==r)
77 {
78 tree[num].l=tree[num].r=l;
79 tree[num].ps=l;
80return;
81 }
82int mid=(l+r)>>1;
83 build(num<<1,l,mid);
84 build((num<<1)|1,mid+1,r);
85 tree[num].l=l,tree[num].r=r;
86 tree[num].ps=tree[(num<<1)|1].ps;
87}
88 89int main()
90{
91longlong ans=0;
92int n,k;
93 n=read(),k=read();
94for(int i=1;i<=n;i++)a[i]=read();
95for(int i=1;i<n;i++)
96 {
97int u,v;
98 u=read();v=read();
99 graph[u].push_back(v);
100 father[v]=u;
101 }
102103 father[1]=0;
104105 DFS(1);
106 build(1,1,n);
107108for(int i=1;i<=n;i++)
109 update(1,dfn[i],last[i],a[i]);
110111while(k--)
112 {
113 psh(1);
114 ans+=tree[1].num;
115int u=rev[tree[1].ps];
116while(u&&!vis[u])
117 {
118 vis[u]=1;
119 update(1,dfn[u],last[u],-a[u]);
120 u=father[u];
121 }
122 }
123 printf("%lld",ans);
124return0;
125 }
(死于太久没打tag。。)
原文：http://www.cnblogs.com/tuigou/p/4848532.html
内容总结
以上是互联网集市为您收集整理的【贪心】 BZOJ 3252:攻略全部内容，希望文章能够帮你解决【贪心】 BZOJ 3252:攻略所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。