企业销售型网站是什么,单品商城网站源码,万州官方网,设计 网站访问次数题目大意
有 n n n样菜品#xff0c;每样菜品都有两个权值 a i a_i ai和 b i b_i bi#xff0c;如果你选择了 k k k个菜品#xff0c;分别为 p 1 , … , p k p_1,\dots,p_k p1,…,pk#xff0c;则你的花费为 ∑ i 1 k a p i max i 1 k b p i \sum\limits_{i…题目大意
有 n n n样菜品每样菜品都有两个权值 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\limits_{i1}^kb_{p_i} i1∑kapii1maxkbpi
对于每个 1 ≤ k ≤ n 1\leq k\leq n 1≤k≤n求如何选 k k k个菜品才能使花费最小并输出最小花费。 1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i , b i ≤ 1 0 9 1\leq n\leq 2\times 10^5,1\leq a_i,b_i\leq 10^9 1≤n≤2×105,1≤ai,bi≤109
时间限制 2000 m s 2000ms 2000ms空间限制 512 M B 512MB 512MB。 题解
前置知识可持久化线段树主席树
首先我们考虑如何求 k k k固定时的答案。将所有菜品按 b b b值从小到大排序如果 b b b值相同则按 a a a值从小到大排序。枚举第 x x x个菜品作为选中的 b b b最大的菜品那么剩下的 k − 1 k-1 k−1个菜品肯定是选择前 x − 1 x-1 x−1个菜品中 a a a最小的 k − 1 k-1 k−1个盘子。对于给定的 k k k和 x x x用可持久化线段树可以用 O ( n log n ) O(n\log n) O(nlogn)的时间复杂度来求出对应方案的值我们将其记为 w ( k , x ) w(k,x) w(k,x)。
令 f ( k ) f(k) f(k)表示在取 k k k个菜品时能得到最优解的 x x x对于两个不同的决策 x , y x,y x,y x y xy xy若 w ( k , x ) ≥ w ( k , y ) w(k,x)\geq w(k,y) w(k,x)≥w(k,y)那么增大 k k k之后因为 y y y的可选择范围包含了 x x x的可选择范围所以 y y y新选的 a a a值一定不大于 x x x新选的 a a a值即 w ( k ′ , x ) ≥ w ( k ′ , y ) w(k,x)\geq w(k,y) w(k′,x)≥w(k′,y)对 k ≤ k ′ ≤ n k\leq k\leq n k≤k′≤n恒成立。由此可得 f ( 1 ) ≤ f ( 2 ) ≤ ⋯ ≤ f ( n ) f(1)\leq f(2)\leq\cdots\leq f(n) f(1)≤f(2)≤⋯≤f(n)即最优决策具有单调性可以用分治求解。
在分治的时候用 s o l v e ( s l , s r , l , r ) solve(sl,sr,l,r) solve(sl,sr,l,r)表示用 x ∈ [ l , r ] x\in [l,r] x∈[l,r]来给 k ∈ [ s l , s r ] k\in [sl,sr] k∈[sl,sr]计算答案。一开始是 s o l v e ( 1 , n , 1 , n ) solve(1,n,1,n) solve(1,n,1,n)将其分成若干个子问题分别来解决。对于每个子问题令 m i d ( s l s r ) / 2 mid(slsr)/2 mid(slsr)/2则我们先在 [ l , r ] [l,r] [l,r]中找到 f ( m i d ) f(mid) f(mid)设 f ( m i d ) p o s f(mid)pos f(mid)pos则 [ s l , m i d − 1 ] [sl,mid-1] [sl,mid−1]的 f f f值在 [ l , p o s ] [l,pos] [l,pos]上 [ m i d 1 , s r ] [mid1,sr] [mid1,sr]的 f f f值在 [ p o s , r ] [pos,r] [pos,r]上那我们就可以将原问题分为两个子问题 s o l v e ( s l , m i d − 1 , l , p o s ) solve(sl,mid-1,l,pos) solve(sl,mid−1,l,pos)和 s o l v e ( m i d 1 , s r , p o s , r ) solve(mid1,sr,pos,r) solve(mid1,sr,pos,r)。
在分治的时候最多只会往下推 O ( log n ) O(\log n) O(logn)层每层需要求 O ( n ) O(n) O(n)个 w ( k , x ) w(k,x) w(k,x)的值总共需要求 O ( n log n ) O(n\log n) O(nlogn)个 w ( k , x ) w(k,x) w(k,x)的值所以时间复杂度为 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)。
code
#includebits/stdc.h
using namespace std;
const int N200000;
int n,tot0,rt[N5],re[N5];
long long ans[N5];
struct node{int a,b;
}w[N5];
struct tree{int lc,rc,hv;long long s;
}tr[N*205];
bool cmp1(node ax,node bx){return ax.abx.a;}
bool cmp2(node ax,node bx){return ax.bbx.b;}
void ch(int r1,int r2,int l,int r,int v){r1tot;tr[r1]tr[r2];if(lr){tr[r1].hv;tr[r1].sre[l];return;}int midlr1;if(vmid) ch(tr[r1].lc,tr[r2].lc,l,mid,v);else ch(tr[r1].rc,tr[r2].rc,mid1,r,v);tr[r1].hvtr[tr[r1].lc].hvtr[tr[r1].rc].hv;tr[r1].str[tr[r1].lc].str[tr[r1].rc].s;
}
long long find(int k,int l,int r,int v){if(lr) return tr[k].s;int midlr1;if(tr[tr[k].lc].hvv) return find(tr[k].lc,l,mid,v);else return find(tr[k].rc,mid1,r,v-tr[tr[k].lc].hv)tr[tr[k].lc].s;
}
void solve(int sl,int sr,int l,int r){if(slsr) return;int midslsr1,pos0;for(int imax(mid,l);ir;i){long long noww[i].bfind(rt[i],1,n,mid);if(ans[mid]now){ans[mid]now;posi;}}solve(sl,mid-1,l,pos);solve(mid1,sr,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,w[i].a,w[i].b);ans[i]1e18;}sort(w1,wn1,cmp1);for(int i1;in;i){re[i]w[i].a;w[i].ai;}sort(w1,wn1,cmp2);for(int i1;in;i) ch(rt[i],rt[i-1],1,n,w[i].a);solve(1,n,1,n);for(int i1;in;i) printf(%lld\n,ans[i]);return 0;
}
文章转载自： http://www.morning.clxpp.cn.gov.cn.clxpp.cn http://www.morning.nkllb.cn.gov.cn.nkllb.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.prmbb.cn.gov.cn.prmbb.cn http://www.morning.ndynz.cn.gov.cn.ndynz.cn http://www.morning.mkygc.cn.gov.cn.mkygc.cn http://www.morning.fpjxs.cn.gov.cn.fpjxs.cn http://www.morning.xqbbc.cn.gov.cn.xqbbc.cn http://www.morning.lxcwh.cn.gov.cn.lxcwh.cn http://www.morning.lznfl.cn.gov.cn.lznfl.cn http://www.morning.zrlwl.cn.gov.cn.zrlwl.cn http://www.morning.rqgjr.cn.gov.cn.rqgjr.cn http://www.morning.ptmch.com.gov.cn.ptmch.com http://www.morning.fpryg.cn.gov.cn.fpryg.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.gqbks.cn.gov.cn.gqbks.cn http://www.morning.slfmp.cn.gov.cn.slfmp.cn http://www.morning.pyzt.cn.gov.cn.pyzt.cn http://www.morning.rqhdt.cn.gov.cn.rqhdt.cn http://www.morning.qgqck.cn.gov.cn.qgqck.cn http://www.morning.qblcm.cn.gov.cn.qblcm.cn http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.qcwrm.cn.gov.cn.qcwrm.cn http://www.morning.gkfwp.cn.gov.cn.gkfwp.cn http://www.morning.nfpgc.cn.gov.cn.nfpgc.cn http://www.morning.wxfgg.cn.gov.cn.wxfgg.cn http://www.morning.mjxgs.cn.gov.cn.mjxgs.cn http://www.morning.smspc.cn.gov.cn.smspc.cn http://www.morning.cjcry.cn.gov.cn.cjcry.cn http://www.morning.wypyl.cn.gov.cn.wypyl.cn http://www.morning.cmdfh.cn.gov.cn.cmdfh.cn http://www.morning.rfpxq.cn.gov.cn.rfpxq.cn http://www.morning.nsfxt.cn.gov.cn.nsfxt.cn http://www.morning.ykrg.cn.gov.cn.ykrg.cn http://www.morning.fgxr.cn.gov.cn.fgxr.cn http://www.morning.ckhpg.cn.gov.cn.ckhpg.cn http://www.morning.bzjpn.cn.gov.cn.bzjpn.cn http://www.morning.tnthd.cn.gov.cn.tnthd.cn http://www.morning.gwqq.cn.gov.cn.gwqq.cn http://www.morning.blfll.cn.gov.cn.blfll.cn http://www.morning.nkbfc.cn.gov.cn.nkbfc.cn http://www.morning.ltkzb.cn.gov.cn.ltkzb.cn http://www.morning.qxxj.cn.gov.cn.qxxj.cn http://www.morning.grlth.cn.gov.cn.grlth.cn http://www.morning.mzwfw.cn.gov.cn.mzwfw.cn http://www.morning.zmwzg.cn.gov.cn.zmwzg.cn http://www.morning.dkcpt.cn.gov.cn.dkcpt.cn http://www.morning.yfddl.cn.gov.cn.yfddl.cn http://www.morning.drywd.cn.gov.cn.drywd.cn http://www.morning.kwrzg.cn.gov.cn.kwrzg.cn http://www.morning.zwsgl.cn.gov.cn.zwsgl.cn http://www.morning.rsbqq.cn.gov.cn.rsbqq.cn http://www.morning.rtzd.cn.gov.cn.rtzd.cn http://www.morning.xwbld.cn.gov.cn.xwbld.cn http://www.morning.xzgbj.cn.gov.cn.xzgbj.cn http://www.morning.cmldr.cn.gov.cn.cmldr.cn http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.htbbp.cn.gov.cn.htbbp.cn http://www.morning.cjmmt.cn.gov.cn.cjmmt.cn http://www.morning.ktlxk.cn.gov.cn.ktlxk.cn http://www.morning.qnypp.cn.gov.cn.qnypp.cn http://www.morning.cknws.cn.gov.cn.cknws.cn http://www.morning.rtkz.cn.gov.cn.rtkz.cn http://www.morning.ckhyj.cn.gov.cn.ckhyj.cn http://www.morning.hbtarq.com.gov.cn.hbtarq.com http://www.morning.xywfz.cn.gov.cn.xywfz.cn http://www.morning.krfpj.cn.gov.cn.krfpj.cn http://www.morning.bgnkl.cn.gov.cn.bgnkl.cn http://www.morning.c7629.cn.gov.cn.c7629.cn http://www.morning.hxrfb.cn.gov.cn.hxrfb.cn http://www.morning.npxht.cn.gov.cn.npxht.cn http://www.morning.bqrd.cn.gov.cn.bqrd.cn http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.xczyj.cn.gov.cn.xczyj.cn http://www.morning.wkcl.cn.gov.cn.wkcl.cn http://www.morning.zwmjq.cn.gov.cn.zwmjq.cn http://www.morning.gyfwy.cn.gov.cn.gyfwy.cn http://www.morning.fhghy.cn.gov.cn.fhghy.cn http://www.morning.grxbw.cn.gov.cn.grxbw.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn
