文章目錄

• 題目描述
• 解析
• • 我的思路
  • • 代碼
  • 題解思路

題目描述

解析

我的思路

其實(shí)就是線段覆蓋的一個(gè)變體
貪心的想：
把游客按右端點(diǎn)升序排序
后面的證明就和線段覆蓋一樣了
如果有兩個(gè)游客沖突
我們應(yīng)該選右端點(diǎn)靠右的
因?yàn)檫@樣對(duì)以后繼續(xù)在右邊出現(xiàn)的游客來說肯定不會(huì)更差

然后就是對(duì)于能否上車的判斷
其實(shí)就是一個(gè)對(duì)區(qū)間的修改與最大值查詢
就非常自然的想到了線段樹

時(shí)間復(fù)雜度：nlogn

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=3e5+100; ll ans; int n,c,k;#define mid ((r+l)>>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(k<<1,add[k]);Add(k<<1|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(x<=l&&r<=y){Add(k,v);return;}pushdown(k);if(x<=mid) change(k<<1,l,mid,x,y,v);if(y>=mid+1) change(k<<1|1,mid+1,r,x,y,v);mx[k]=max(mx[k<<1],mx[k<<1|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(x<=l&&r<=y){ // printf("l=%d r=%d res=%d\n",l,r,mx[k]);return mx[k];}pushdown(k);int res=0;if(x<=mid) res=max(res,ask(k<<1,l,mid,x,y));if(y>=mid+1) res=max(res,ask(k<<1|1,mid+1,r,x,y)); // printf("l=%d r=%d res=%d\n",l,r,res);mx[k]=max(mx[k<<1],mx[k<<1|1]);return res; }struct node{int x,y,num;bool operator < (const node o)const{return y<o.y;} }p[N]; int main(){scanf("%d%d%d",&k,&n,&c);for(int i=1;i<=k;i++){scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].num);} sort(p+1,p+1+k);for(int i=1;i<=k;i++){int xx=p[i].x,yy=p[i].y,nn=p[i].num;int ad=min(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);ans+=ad;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 */

題解思路

突然想到這道二叉堆的題自己似乎并沒有用到二叉堆。。。
于是又看了下題解

大概思路就是：
每到一站，只要沒滿就讓游客上來
如果滿了，就強(qiáng)制讓目的地最靠后的游客下車
當(dāng)然，已經(jīng)到站的下車就行（在這個(gè)策略下到站的已經(jīng)就是堆頂元素）
對(duì)于那些沒到站就被迫下車的游客，等價(jià)于沒有讓他們上車

這樣就不用寫線段樹了，碼量減少許多；而且思路也很妙

小技巧：對(duì)于一些由于后續(xù)情況而當(dāng)前不知道是否選擇的決策，可以暫時(shí)先選上，與更優(yōu)決策與它沖突時(shí)再放棄，這樣也就等價(jià)與沒有選擇

總結(jié)

以上是生活随笔為你收集整理的火车载客（ybtoj-二叉堆）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。