洛谷P1552 派遣

2022-09-23 02:12:11 字數 1808 閱讀 6860

在這個幫派裡,有一名忍者被稱之為 master。除了 master 以外,每名忍者都有且僅有一個上級。為保密,同時增強忍者們的領導力,所有與他們工作相關的指令總是由上級傳送給他的直接下屬,而不允許通過其他的方式傳送。

現在你要招募一批忍者,並把它們派遣給顧客。你需要為每個被派遣的忍者支付一定的薪水,同時使得支付的薪水總額不超過你的預算。另外,為了傳送指令,你需要選擇一名忍者作為管理者,要求這個管理者可以向所有被派遣的忍者傳送指令,在傳送指令時,任何忍者(不管是否被派遣)都可以作為訊息的傳遞人。管理者自己可以被派遣,也可以不被派遣。當然,如果管理者沒有被排遣,你就不需要支付管理者的薪水。

你的目標是在預算內使顧客的滿意度最大。這裡定義顧客的滿意度為派遣的忍者總數乘以管理者的領導力水平,其中每個忍者的領導力水平也是一定的。

寫一個程式,給定每一個忍者 \(i\) 的上級 \(b_i\),薪水 \(c_i\),領導力 \(l_i\),以及支付給忍者們的薪水總預算 \(m\),輸出在預算內滿足上述要求時顧客滿意度的最大值。

眾所周知這是一道左偏樹的模板題。所以我們考慮線段樹。

習慣性,設 \(a_i\) 表示薪水,\(b_i\) 表示領導力。

考慮列舉每一個點 \(x\) 作為管理者,那麼顯然為了使滿意度最大,我們要在 \(x\) 為根的子樹中選擇儘量多的點,同時滿足 \(\sum_ a_y\leq m\)。

所以肯定選擇薪水最小的若干個。到這裡左偏樹的思路已經完全出來了。

不會左偏樹怎麼辦?其實可以用權值線段樹解決。設 \(rk[i]\) 表示第 \(i\) 個忍者的薪水是第幾小的,對於一個點 \(x\),如果我們可以把位於 \(x\) 的子樹裡的點插入進以 \(rk\) 為下標的權值線段樹,那麼就可以輕鬆的求出最多能選擇多少個忍者。

如何維護這 \(n\) 個線段樹呢?直接從下往上權值線段樹合併即可。

時間複雜度 \(o(n\log n)\)。

#include #include #include #include #define mp make_pair

using namespace std;

typedef long long ll;

const int n=100010;

int n,m,tot,root,head[n],rt[n],a[n],b[n],rk[n];

ll ans;

priority_queue> q;

struct edge

e[n];

void add(int from,int to)

struct segtree

int update(int x,int l,int r,int k,int val)

int mid=(l+r)>>1;

if (k<=mid) lc[x]=update(lc[x],l,mid,k,val);

else rc[x]=update(rc[x],mid+1,r,k,val);

pushup(x);

return x; }

int merge(int x,int y)

ll query(int x,int l,int r,int k)

}seg;

void dfs(int x)

rt[x]=seg.update(rt[x],1,n,rk[x],a[x]);

ans=max(ans,1ll*b[x]*seg.query(rt[x],1,n,m));

}int main()

for (int i=1;i<=n;i++)

dfs(root);

printf("%lld",ans);

return 0;

}

P1552 APIO2012 派遣

複習下左偏樹 左偏樹首先滿足堆性質,其次定義了一個dis,使得每個點的dis都是右子樹dis 1,且左子樹的dis 右子樹的dis 合併過程可以參考fhq treap的merge進行修改 一開始看錯題了,是選擇的人要能跟所有派遣者通訊 等價於是選擇子樹中的點 ,不是選中一個人使他變得可以與所有人通訊...

洛谷1552 APIO2012 派遣

luogu上被刷到了省選 noi 。。。不至於吧 這題似乎有很多辦法亂搞? 對於一個點,如果他當管理者,那選的肯定是他子樹中薪水最少的k個,...

洛谷 P5509 派遣

題目傳送門 心路歷程 每想到一種思路,就有一種要做出來的感覺。但一接著想就會發現這種方法有一些極小的問題,但是我沒法解決。。。 於是就再換思...