营销型网站建设方法,软件外包公司人数,天津市建设工程评标专家网,电子商务网站购物车怎么做一家新的餐馆开业了#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]);
}
