国内最大的摄影网站,建设一个大型网站需要多少钱,做官网需要多少钱,wordpress弹窗通知一家新的餐馆开业了#xff0c;为了吸引更多的顾客#xff0c;每样餐品都有打折的活动。特别的#xff0c;餐馆内一共有#x1d45b;样菜品#xff0c;编号从 1 1 1 到 n n n#xff0c;每样菜品每人最多只能点一次。对于第 i i i 种菜品#xff0c;其包含两种价格为了吸引更多的顾客每样餐品都有打折的活动。特别的餐馆内一共有样菜品编号从 1 1 1 到 n n n每样菜品每人最多只能点一次。对于第 i i i 种菜品其包含两种价格活动价格 a i a_i ai 与差价 b i b_i bi。
假设某顾客点了 k k k 样菜品依次编号为 p 1 , … , p k p_1,\dots,p_k p1,…,pk那么最终需要支付的价格为 ∑ i 1 k a p i max i 1 k b p i \sum\limits_{i1}^ka_{p_i}\max_{i1}^kb_{p_i} i1∑kapii1maxkbpi
现在有 n n n 名顾客光顾这家餐馆第 i i i 名顾客想恰好点 i i i 样菜品请帮助每位顾客计算出他的最小花费。 n ≤ 2 × 1 0 5 n\le2\times10^5 n≤2×105 先把菜品按 b b b 从小到大排序如果当前要点 k k k 个菜选定第 i i i 个菜那么就是要在前 i − 1 i-1 i−1 个菜中选 k − 1 k-1 k−1 个菜。
可以用 set 维护或者主席树时间复杂度 O ( n 2 log n ) O(n^2\log n) O(n2logn)这是暴力。
设 w ( k , i ) w(k,i) w(k,i) 表示前 i i i 个菜中选 k k k 个菜的最小花费 f ( k ) f(k) f(k) 为使 w ( k , i ) w(k,i) w(k,i) 取得最小值的 i i i。
考虑决策 x y xy xy若 w ( k , x ) ≥ w ( k , y ) w(k,x)\ge w(k,y) w(k,x)≥w(k,y)增大 k k k 后 y y y 可选的菜品比 x x x 的多所以 ∀ k ′ ∈ ( k , n ] , w ( k ′ , x ) ≥ w ( k ′ , y ) \forall k\in(k,n],w(k,x)\ge w(k,y) ∀k′∈(k,n],w(k′,x)≥w(k′,y)若 y f ( k ) yf(k) yf(k)则对于后面的决策点 m m m w w w 值至少都比前面的要小了所以 f ( k ) ≤ f ( m ) f(k)\le f(m) f(k)≤f(m)即 f ( 1 ) ≤ f ( 2 ) ≤ ⋯ ≤ f ( n ) f(1)\le f(2)\le\dots\le f(n) f(1)≤f(2)≤⋯≤f(n)决策具有单调性。
如果这是 DP就可以用 1D/1D 动态规划的优化方法 O ( n log n ) O(n\log n) O(nlogn) 拿下。但是这不是。
这里要用分治的思想函数 s o l v e ( l , r , L , R ) solve(l,r,L,R) solve(l,r,L,R) 表示当前处理到区间 [ l , r ] [l,r] [l,r] m i d mid mid 的最优决策点在 L , R L,R L,R。每次暴力求出 p o s f ( m i d ) posf(mid) posf(mid)把问题分成 s o l v e ( l , m i d − 1 , L , p o s ) solve(l,mid-1,L,pos) solve(l,mid−1,L,pos) 和 s o l v e ( m i d 1 , r , p o s , R ) solve(mid1,r,pos,R) solve(mid1,r,pos,R) 两部分这样递归处理下去。
求一个 w w w 是 O ( log V ) O(\log V) O(logV) 的总的时间复杂度为 O ( n log n log V ) O(n\log n\log V) O(nlognlogV)。 V V V 是值域
代码如下
#includebits/stdc.h
using namespace std;
typedef long long ll;
const ll INF1e18,Inf1e9;
const int N2e51;
int n,A[N],cnt,rt[N];
ll ans[N];
struct node
{int a,b;bool operator(const node a)const{return ba.b;}
}a[N];
struct Node
{int ls,rs,sz;ll sum;
}tr[N*32];
void insert(int rt,int la,int l,int r,int x)
{rtcnt;tr[rt]tr[la];tr[rt].sz;tr[rt].sumx;if(lr) return;int midlr1;if(xmid) insert(tr[rt].ls,tr[la].ls,l,mid,x);else insert(tr[rt].rs,tr[la].rs,mid1,r,x);
}
ll query(int rt,int l,int r,int k)
{if(lr) return k*l;int midlr1,sumtr[tr[rt].ls].sz;if(sumk) return query(tr[rt].ls,l,mid,k);else return query(tr[rt].rs,mid1,r,k-sum)tr[tr[rt].ls].sum;
}
void solve(int l,int r,int L,int R)
{if(rl) return;int midlr1,pos;ll sumINF;for(int imax(mid,L);iR;i){ll xa[i].ba[i].aquery(rt[i-1],0,Inf,mid-1);if(sumx){sumx;posi;}}ans[mid]sum;solve(l,mid-1,L,pos);solve(mid1,r,pos,R);
}
int main()
{freopen(order.in,r,stdin);freopen(order.out,w,stdout);scanf(%d,n);for(int i1;in;i) scanf(%d%d,a[i].a,a[i].b);sort(a1,a1n);for(int i1;in;i) insert(rt[i],rt[i-1],0,Inf,a[i].a);solve(1,n,1,n);for(int i1;in;i) printf(%lld\n,ans[i]);
}
文章转载自： http://www.morning.rjbb.cn.gov.cn.rjbb.cn http://www.morning.rytps.cn.gov.cn.rytps.cn http://www.morning.bzlgb.cn.gov.cn.bzlgb.cn http://www.morning.hrgxk.cn.gov.cn.hrgxk.cn http://www.morning.gcbhh.cn.gov.cn.gcbhh.cn http://www.morning.ptslx.cn.gov.cn.ptslx.cn http://www.morning.gkpgj.cn.gov.cn.gkpgj.cn http://www.morning.lrjtx.cn.gov.cn.lrjtx.cn http://www.morning.zfgh.cn.gov.cn.zfgh.cn http://www.morning.bauul.com.gov.cn.bauul.com http://www.morning.lzqtn.cn.gov.cn.lzqtn.cn http://www.morning.jkzjs.cn.gov.cn.jkzjs.cn http://www.morning.qcsbs.cn.gov.cn.qcsbs.cn http://www.morning.zpzys.cn.gov.cn.zpzys.cn http://www.morning.vtbtje.cn.gov.cn.vtbtje.cn http://www.morning.rfldz.cn.gov.cn.rfldz.cn http://www.morning.rbjf.cn.gov.cn.rbjf.cn http://www.morning.wrbx.cn.gov.cn.wrbx.cn http://www.morning.gcftl.cn.gov.cn.gcftl.cn http://www.morning.clfct.cn.gov.cn.clfct.cn http://www.morning.qgjxy.cn.gov.cn.qgjxy.cn http://www.morning.gqtzb.cn.gov.cn.gqtzb.cn http://www.morning.tsdjj.cn.gov.cn.tsdjj.cn http://www.morning.nlywq.cn.gov.cn.nlywq.cn http://www.morning.hxycm.cn.gov.cn.hxycm.cn http://www.morning.fxzgw.com.gov.cn.fxzgw.com http://www.morning.sgpnz.cn.gov.cn.sgpnz.cn http://www.morning.dmhs.cn.gov.cn.dmhs.cn http://www.morning.tpchy.cn.gov.cn.tpchy.cn http://www.morning.wwnb.cn.gov.cn.wwnb.cn http://www.morning.fhghy.cn.gov.cn.fhghy.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.jljwk.cn.gov.cn.jljwk.cn http://www.morning.rmfw.cn.gov.cn.rmfw.cn http://www.morning.gbyng.cn.gov.cn.gbyng.cn http://www.morning.bmtkp.cn.gov.cn.bmtkp.cn http://www.morning.lgtzd.cn.gov.cn.lgtzd.cn http://www.morning.pamdeer.com.gov.cn.pamdeer.com http://www.morning.rwhlf.cn.gov.cn.rwhlf.cn http://www.morning.kjtdy.cn.gov.cn.kjtdy.cn http://www.morning.wkmyt.cn.gov.cn.wkmyt.cn http://www.morning.zkbxx.cn.gov.cn.zkbxx.cn http://www.morning.rwtlj.cn.gov.cn.rwtlj.cn http://www.morning.wjhnx.cn.gov.cn.wjhnx.cn http://www.morning.ztqyj.cn.gov.cn.ztqyj.cn http://www.morning.fwwkr.cn.gov.cn.fwwkr.cn http://www.morning.qtwd.cn.gov.cn.qtwd.cn http://www.morning.zgpgl.cn.gov.cn.zgpgl.cn http://www.morning.gcysq.cn.gov.cn.gcysq.cn http://www.morning.nykzl.cn.gov.cn.nykzl.cn http://www.morning.lwyqd.cn.gov.cn.lwyqd.cn http://www.morning.qhrdx.cn.gov.cn.qhrdx.cn http://www.morning.sgjw.cn.gov.cn.sgjw.cn http://www.morning.bmjfp.cn.gov.cn.bmjfp.cn http://www.morning.ylph.cn.gov.cn.ylph.cn http://www.morning.hxmqb.cn.gov.cn.hxmqb.cn http://www.morning.zxwqt.cn.gov.cn.zxwqt.cn http://www.morning.jwxnr.cn.gov.cn.jwxnr.cn http://www.morning.ldfcb.cn.gov.cn.ldfcb.cn http://www.morning.jycr.cn.gov.cn.jycr.cn http://www.morning.ktrdc.cn.gov.cn.ktrdc.cn http://www.morning.tynqy.cn.gov.cn.tynqy.cn http://www.morning.rdmn.cn.gov.cn.rdmn.cn http://www.morning.nmlpp.cn.gov.cn.nmlpp.cn http://www.morning.mdwtm.cn.gov.cn.mdwtm.cn http://www.morning.dbjyb.cn.gov.cn.dbjyb.cn http://www.morning.gjlml.cn.gov.cn.gjlml.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.plqqp.cn.gov.cn.plqqp.cn http://www.morning.hrpjx.cn.gov.cn.hrpjx.cn http://www.morning.grpfj.cn.gov.cn.grpfj.cn http://www.morning.pqndg.cn.gov.cn.pqndg.cn http://www.morning.nnttr.cn.gov.cn.nnttr.cn http://www.morning.srndk.cn.gov.cn.srndk.cn http://www.morning.ljdtn.cn.gov.cn.ljdtn.cn http://www.morning.pprxs.cn.gov.cn.pprxs.cn http://www.morning.kxwsn.cn.gov.cn.kxwsn.cn http://www.morning.jthjr.cn.gov.cn.jthjr.cn http://www.morning.wphzr.cn.gov.cn.wphzr.cn
