ABC 289 G - Shopping in AtCoder store 数学推导+凸包

大意：
n个顾客，每个人有一个购买的欲望bi,m件物品，每一件物品有一个价值ci,每一个顾客会买商品当且仅当bi+ci>=定价.

现在要求对每一个商品定价，求出它的最大销售值（数量*定价）

n,m<=2e5

思路：

首先m件物品都是相互独立的，可以看成m个询问

另外，不妨对n个人的购买力做一个降序排序，显然它们满足单调性

不难发现，一旦我们定下了物品的价格，那么最终的销售额就由销售数量决定，也就是会有多少人买。此时在销售数量减少的情况下，我们一定会尽可能地抬高价格。从而我们得到一个结论:每一个商品i的定价一定是bj+ci(1<=j<=n).这是因为，它刚好可以使某个人会买这件商品。假设最优定价不满足这个结论，显然我们可以直接抬高它使其达到另一个bj+ci，此时我们在购买人数不变的情况下就提高了单价，这是更优的。

现在商品单价就只有n个选择了，对于商品i，我们的销售额就是max{j*(bj+ci)}(1<=j<=n),因为我们是按购买力降序排序，如果第j个人刚好买的起，那么前面的人一定都买的起（这里也不用关心购买力重复的问题，因为重复的话，后面相同购买力的的人对应的决策一定会更好）。

此时我们就转化了题意：对于一个i(1<=i<=m),找到max{j*(bj+ci)}

这里借一下官方题解的图片：

 我们令横坐标为ci，纵坐标为对应的价值，不同j的选择对应不同的总价值。显然我们最后是要找一个凸包，最后的答案就是横坐标对应的凸包上的点的纵坐标了

求凸包的话，我们从1-n开始遍历的话，直线的斜率是单调递增的，

 不妨用单调栈来更新当前段的最大值对应的直线

假设当前栈内有两条直线L0,L1,交点为X_01,那么对于新加入的直线L',如果它与L0的交点X_1'的横坐标小于X_01的横坐标，显然就可以把L1淘汰掉了，因为它后面也不会有比L‘更大的机会了。

关于这个判断，就只要计算一下交点横坐标就可以了。

最后我们得到了一个凸包，那么对于一个ci，我们去二分找到它在那一段线段上就可以了

时间复杂度O(n+mlogn)

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mk make_pair
const ll N=2e5+10;
ll n,m;
ll b[N];
ll c[N];
struct P
{double x,y;
};
vector<pair<double,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].first<=tar;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;++i) cin>>b[i];sort(b+1,b+1+n,greater<ll>());for(int i=1;i<=m;++i) cin>>c[i];for(int i=1;i<=n;++i){P p={(double)i,(double)i*b[i]};//y=ix+i*b[i]while(vt.size()>=2&&cross(p,vt.rbegin()->second,(next(vt.rbegin()))->second)<0) vt.pop_back();//弹出无用的直线double x=0;if(vt.size()){P pp=vt.back().second;x=(pp.y-p.y)/(p.x-pp.x);} vt.push_back(make_pair(x,p));}	ll len=vt.size();
//	for(auto i:vt)
//	{
//		cout<<i.second.x<<" "<<i.second.y<<endl;
//	}for(int i=1;i<=m;++i){ll l=0,r=len-1;while(l<=r){ll mid=l+r>>1;if(judge(mid,c[i])) l=mid+1;else r=mid-1;}P op=vt[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;cin>>t;while(t--)solve();return 0;
}