舟山网站建设流程,网站建设单位是什么意思,开锁做网站哪个好,关键词优化排名文章目录题目描述解析我的思路代码题解思路题目描述 解析
我的思路
其实就是线段覆盖的一个变体 贪心的想#xff1a; 把游客按右端点升序排序 后面的证明就和线段覆盖一样了 如果有两个游客冲突 我们应该选右端点靠右的 因为这样对以后继续在右边出现的游客来说肯定不会更差…
文章目录题目描述解析我的思路代码题解思路题目描述 解析
我的思路
其实就是线段覆盖的一个变体 贪心的想 把游客按右端点升序排序 后面的证明就和线段覆盖一样了 如果有两个游客冲突 我们应该选右端点靠右的 因为这样对以后继续在右边出现的游客来说肯定不会更差
然后就是对于能否上车的判断 其实就是一个对区间的修改与最大值查询 就非常自然的想到了线段树
时间复杂度nlogn
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N3e5100;
ll ans;
int n,c,k;#define mid ((rl)1)
int mx[4*N],add[4*N];
void Add(int k,int v){add[k]v;mx[k]v;return;
}
void pushdown(int k){if(add[k]0) return;Add(k1,add[k]);Add(k1|1,add[k]);add[k]0;
}
void change(int k,int l,int r,int x,int y,int v){
// printf(l%d r%d x%d y%d\n,l,r,x,y);if(xlry){Add(k,v);return;}pushdown(k);if(xmid) change(k1,l,mid,x,y,v);if(ymid1) change(k1|1,mid1,r,x,y,v);mx[k]max(mx[k1],mx[k1|1]);return;
}
int ask(int k,int l,int r,int x,int y){
// printf(l%d r%d x%d y%d\n,l,r,x,y);if(xlry){
// printf(l%d r%d res%d\n,l,r,mx[k]);return mx[k];}pushdown(k);int res0;if(xmid) resmax(res,ask(k1,l,mid,x,y));if(ymid1) resmax(res,ask(k1|1,mid1,r,x,y));
// printf(l%d r%d res%d\n,l,r,res);mx[k]max(mx[k1],mx[k1|1]);return res;
}struct node{int x,y,num;bool operator (const node o)const{return yo.y;}
}p[N];
int main(){scanf(%d%d%d,k,n,c);for(int i1;ik;i){scanf(%d%d%d,p[i].x,p[i].y,p[i].num);} sort(p1,p1k);for(int i1;ik;i){int xxp[i].x,yyp[i].y,nnp[i].num;int admin(nn,c-ask(1,1,n,xx,yy-1));
// printf(i%d ad%d ask%d\n,i,ad,ask(1,1,n,xx,yy));
// printf(x%d y%d ad%d\n\n,xx,yy-1,ad);ansad;change(1,1,n,xx,yy-1,ad);}printf(%lld,ans);
}
/*
in:
8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1
out:10
*/
题解思路
突然想到这道二叉堆的题自己似乎并没有用到二叉堆。。。 于是又看了下题解
大概思路就是 每到一站只要没满就让游客上来 如果满了就强制让目的地最靠后的游客下车 当然已经到站的下车就行在这个策略下到站的已经就是堆顶元素 对于那些没到站就被迫下车的游客等价于没有让他们上车
这样就不用写线段树了码量减少许多而且思路也很妙 小技巧对于一些由于后续情况而当前不知道是否选择的决策可以暂时先选上与更优决策与它冲突时再放弃这样也就等价与没有选择
