福州建设局网站,wordpress 分类目录 404,wordpress给文章区分"原创"和"非原创"的印章,甘德网站建设大意#xff1a; n个顾客#xff0c;每个人有一个购买的欲望bi,m件物品#xff0c;每一件物品有一个价值ci,每一个顾客会买商品当且仅当bici定价.
现在要求对每一个商品定价#xff0c;求出它的最大销售值#xff08;数量*定价#xff09;
n,m2e5
思路#x…大意 n个顾客每个人有一个购买的欲望bi,m件物品每一件物品有一个价值ci,每一个顾客会买商品当且仅当bici定价.
现在要求对每一个商品定价求出它的最大销售值数量*定价
n,m2e5
思路
首先m件物品都是相互独立的可以看成m个询问
另外不妨对n个人的购买力做一个降序排序显然它们满足单调性
不难发现一旦我们定下了物品的价格那么最终的销售额就由销售数量决定也就是会有多少人买。此时在销售数量减少的情况下我们一定会尽可能地抬高价格。从而我们得到一个结论:每一个商品i的定价一定是bjci(1jn).这是因为它刚好可以使某个人会买这件商品。假设最优定价不满足这个结论显然我们可以直接抬高它使其达到另一个bjci此时我们在购买人数不变的情况下就提高了单价这是更优的。
现在商品单价就只有n个选择了对于商品i我们的销售额就是max{j*(bjci)}(1jn),因为我们是按购买力降序排序如果第j个人刚好买的起那么前面的人一定都买的起这里也不用关心购买力重复的问题因为重复的话后面相同购买力的的人对应的决策一定会更好。
此时我们就转化了题意对于一个i(1im),找到max{j*(bjci)}
这里借一下官方题解的图片 我们令横坐标为ci纵坐标为对应的价值不同j的选择对应不同的总价值。显然我们最后是要找一个凸包最后的答案就是横坐标对应的凸包上的点的纵坐标了
求凸包的话我们从1-n开始遍历的话直线的斜率是单调递增的 不妨用单调栈来更新当前段的最大值对应的直线
假设当前栈内有两条直线L0,L1,交点为X_01,那么对于新加入的直线L,如果它与L0的交点X_1的横坐标小于X_01的横坐标显然就可以把L1淘汰掉了因为它后面也不会有比L‘更大的机会了。
关于这个判断就只要计算一下交点横坐标就可以了。
最后我们得到了一个凸包那么对于一个ci我们去二分找到它在那一段线段上就可以了
时间复杂度O(nmlogn)
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
#define mk make_pair
const ll N2e510;
ll n,m;
ll b[N];
ll c[N];
struct P
{double x,y;
};
vectorpairdouble,P vt;
double cross(P p1,P p2,P p3) {return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
bool judge(ll x,ll tar)
{return vt[x].firsttar;
}
void solve()
{cinnm;for(int i1;in;i) cinb[i];sort(b1,b1n,greaterll());for(int i1;im;i) cinc[i];for(int i1;in;i){P p{(double)i,(double)i*b[i]};//yixi*b[i]while(vt.size()2cross(p,vt.rbegin()-second,(next(vt.rbegin()))-second)0) vt.pop_back();//弹出无用的直线double x0;if(vt.size()){P ppvt.back().second;x(pp.y-p.y)/(p.x-pp.x);} vt.push_back(make_pair(x,p));} ll lenvt.size();
// for(auto i:vt)
// {
// couti.second.x i.second.yendl;
// }for(int i1;im;i){ll l0,rlen-1;while(lr){ll midlr1;if(judge(mid,c[i])) lmid1;else rmid-1;}P opvt[l-1].second;cout(ll)(op.x*c[i]op.y) ;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// ll t;cint;while(t--)solve();return 0;
}
