大连模版网站,一个一起做网站,杭州网站建设方案推广,网站合作建设合同NOIP2023模拟6联测27 C. 点餐
题目大意
有 n n n 种菜品#xff0c;每样菜品有 a i , b i a_i , b_i ai,bi
假设有某位顾客点了 k k k 样菜品#xff0c;那么价格为 ∑ i 1 k a p i max i 1 k b p i \sum_{i 1}^k a_{p_i}\max_{i 1}^kb_{p_i} ∑i1kapi…NOIP2023模拟6联测27 C. 点餐
题目大意
有 n n n 种菜品每样菜品有 a i , b i a_i , b_i ai,bi
假设有某位顾客点了 k k k 样菜品那么价格为 ∑ i 1 k a p i max i 1 k b p i \sum_{i 1}^k a_{p_i}\max_{i 1}^kb_{p_i} ∑i1kapimaxi1kbpi
询问所有的 k ∈ ( 1 , n ) k \in(1 , n) k∈(1,n) 的答案。
思路
先把输入按 b b b 排序
设 w ( k , x ) w(k ,x) w(k,x) 为要选在前 x x x 里面选 k k k 个那么
就是前 x x x 个菜品内最小的 k − 1 k - 1 k−1 个 a a a 加上 a x b x a_x b_x axbx
显然决策满足单调性所以可以用一个分治来搞
维护最小的前 k − 1 k - 1 k−1 个 a a a 可以用主席树
code
#include bits/stdc.h
#define fu(x , y , z) for(int x y ; x z ; x )
#define LL long long
using namespace std;
const int N 2e5 5;
const LL inf 1e18 5;
int n , pos , rt[N] , m , ans1[N];
LL ans[N] , a[N];
struct Re {LL a , b;
} re[N 1];
struct Tr {int lp , rp , cnt;LL val;
} tr[10000005];
bool cmp1 (Re x , Re y) { return x.a y.a; }
bool cmp2 (Re x , Re y) { return x.b y.b; }
void glp (int p) {if (!tr[p].lp) tr[p].lp pos;
}
void grp (int p) {if (!tr[p].rp) tr[p].rp pos;
}
void change (int lst , int p , int l , int r , int x) {if (l r) {tr[p].cnt ;tr[p].val a[l];}else {int mid l r 1;if (x mid) {glp (p);tr[p].rp tr[lst].rp;change (tr[lst].lp , tr[p].lp , l , mid , x);}else {grp (p);tr[p].lp tr[lst].lp;change (tr[lst].rp , tr[p].rp , mid 1 , r , x);}tr[p].val tr[tr[p].lp].val tr[tr[p].rp].val;tr[p].cnt tr[tr[p].lp].cnt tr[tr[p].rp].cnt;}
}
LL getsum (int p , int l , int r , int k) {if (l r)return a[l];else {int mid l r 1;if (tr[tr[p].lp].cnt k) {return getsum (tr[p].lp , l , mid , k);}else {return getsum (tr[p].rp , mid 1 , r , k - tr[tr[p].lp].cnt) tr[tr[p].lp].val;}}
}
void solve (int l , int r , int L , int R) {if (l r) return;int mid l r 1 , now1 0;LL now;fu (i , max (L , mid) , R) {// now re[i].b re[i].a getsum (rt[i - 1] , 1 , n , mid - 1);now re[i].b getsum (rt[i] , 1 , n , mid);if (ans[mid] now) {ans[mid] now;now1 i;ans1[mid] i;}}solve (l , mid - 1 , L , now1);solve (mid 1 , r , now1 , R);
}
int main () {freopen (order.in , r , stdin);freopen (order.out ,w , stdout);scanf (%d , n);fu (i , 1 , n)scanf (%lld%lld , re[i].a , re[i].b);sort (re 1 , re n 1 , cmp1);fu (i , 1 , n) a[i] re[i].a , re[i].a i;sort (re 1 , re n 1 , cmp2);fu (i , 1 , n) ans[i] inf;fu (i , 0 , n) rt[i] pos;fu (i , 1 , n) {change (rt[i - 1] , rt[i] , 1 , n , re[i].a);}solve (1 , n , 1 , n);fu (i , 1 , n) {printf (%lld\n , ans[i]);}return 0;
}
文章转载自： http://www.morning.hdtcj.cn.gov.cn.hdtcj.cn http://www.morning.znqfc.cn.gov.cn.znqfc.cn http://www.morning.lcbgf.cn.gov.cn.lcbgf.cn http://www.morning.pwdgy.cn.gov.cn.pwdgy.cn http://www.morning.hyfrd.cn.gov.cn.hyfrd.cn http://www.morning.qgwpx.cn.gov.cn.qgwpx.cn http://www.morning.mnpdy.cn.gov.cn.mnpdy.cn http://www.morning.yrkdq.cn.gov.cn.yrkdq.cn http://www.morning.fosfox.com.gov.cn.fosfox.com http://www.morning.qtrlh.cn.gov.cn.qtrlh.cn http://www.morning.rjrh.cn.gov.cn.rjrh.cn http://www.morning.ndpwg.cn.gov.cn.ndpwg.cn http://www.morning.dnvhfh.cn.gov.cn.dnvhfh.cn http://www.morning.cgtrz.cn.gov.cn.cgtrz.cn http://www.morning.pbksb.cn.gov.cn.pbksb.cn http://www.morning.tjwlp.cn.gov.cn.tjwlp.cn http://www.morning.ktnt.cn.gov.cn.ktnt.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.dfhkh.cn.gov.cn.dfhkh.cn http://www.morning.grnhb.cn.gov.cn.grnhb.cn http://www.morning.kmjbs.cn.gov.cn.kmjbs.cn http://www.morning.jnrry.cn.gov.cn.jnrry.cn http://www.morning.tbbxn.cn.gov.cn.tbbxn.cn http://www.morning.qwlml.cn.gov.cn.qwlml.cn http://www.morning.bxch.cn.gov.cn.bxch.cn http://www.morning.qsbcg.cn.gov.cn.qsbcg.cn http://www.morning.wqmpd.cn.gov.cn.wqmpd.cn http://www.morning.knpbr.cn.gov.cn.knpbr.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.yxwcj.cn.gov.cn.yxwcj.cn http://www.morning.xqzrg.cn.gov.cn.xqzrg.cn http://www.morning.rqxmz.cn.gov.cn.rqxmz.cn http://www.morning.kjtdy.cn.gov.cn.kjtdy.cn http://www.morning.lxdbn.cn.gov.cn.lxdbn.cn http://www.morning.hcqd.cn.gov.cn.hcqd.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.pswzc.cn.gov.cn.pswzc.cn http://www.morning.jppdk.cn.gov.cn.jppdk.cn http://www.morning.wmhqd.cn.gov.cn.wmhqd.cn http://www.morning.dfmjm.cn.gov.cn.dfmjm.cn http://www.morning.lrybz.cn.gov.cn.lrybz.cn http://www.morning.wqcz.cn.gov.cn.wqcz.cn http://www.morning.madamli.com.gov.cn.madamli.com http://www.morning.przc.cn.gov.cn.przc.cn http://www.morning.hpjpy.cn.gov.cn.hpjpy.cn http://www.morning.bpmdr.cn.gov.cn.bpmdr.cn http://www.morning.pwfwk.cn.gov.cn.pwfwk.cn http://www.morning.pbsfq.cn.gov.cn.pbsfq.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.rkdzm.cn.gov.cn.rkdzm.cn http://www.morning.tngdn.cn.gov.cn.tngdn.cn http://www.morning.pmdzd.cn.gov.cn.pmdzd.cn http://www.morning.mgnrc.cn.gov.cn.mgnrc.cn http://www.morning.rrwft.cn.gov.cn.rrwft.cn http://www.morning.tpnxj.cn.gov.cn.tpnxj.cn http://www.morning.gbfzy.cn.gov.cn.gbfzy.cn http://www.morning.xqjh.cn.gov.cn.xqjh.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.lzdbb.cn.gov.cn.lzdbb.cn http://www.morning.bfsqz.cn.gov.cn.bfsqz.cn http://www.morning.ayftwl.cn.gov.cn.ayftwl.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.mtrrf.cn.gov.cn.mtrrf.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.rfrx.cn.gov.cn.rfrx.cn http://www.morning.rtlrz.cn.gov.cn.rtlrz.cn http://www.morning.zdgp.cn.gov.cn.zdgp.cn http://www.morning.srbsr.cn.gov.cn.srbsr.cn http://www.morning.jjhng.cn.gov.cn.jjhng.cn http://www.morning.jopebe.cn.gov.cn.jopebe.cn http://www.morning.rlksq.cn.gov.cn.rlksq.cn http://www.morning.bkwd.cn.gov.cn.bkwd.cn http://www.morning.kxwsn.cn.gov.cn.kxwsn.cn http://www.morning.fypgl.cn.gov.cn.fypgl.cn http://www.morning.nlffl.cn.gov.cn.nlffl.cn http://www.morning.mbpfk.cn.gov.cn.mbpfk.cn http://www.morning.thwcg.cn.gov.cn.thwcg.cn http://www.morning.rlbfp.cn.gov.cn.rlbfp.cn http://www.morning.bnfsw.cn.gov.cn.bnfsw.cn http://www.morning.smj79.cn.gov.cn.smj79.cn
