本文共 1680 字，大约阅读时间需要 5 分钟。

$n$个物品,限定选择$m$个物品求最大/最小权值。

当然具体怎么计算权值按照题目的意思来定

设$g(x)$表示强制选择$x$个物品能得到的最大权值

且$(x,g(x))$在平面上形成一个凸函数,就可以使用$wqs$二分

思想是,我们知道这个凸包的大概形状,但是不知道具体的点$(x,g(x))$(直接求复杂度高)

考虑用一条斜率为$k$的直线去切这个凸包,可以得到一个切点,满足过这个切点截距最大

设这条直线是$y=kx+b$,设过点$(x,g(x))$,那么可以计算出截距$b=g(x)-kx$

现在让$b$最大的时候就是切点,也就是当$g(x)-kx$最大时的$x$值

观察$kx$这一项,可以看成每多选一个物品获得$-k$的权值

于是我们先把所有物品权值减去$k$然后求$g(x)$的最大值即可

由于不限制选几个物品,所以$g(x)$的最大值一般能在$O(n)$的时间内求得,同时可以得到此时取到最大的$x$

现在有什么用呢??

我们知道,由于这是一个上凸壳,斜率递减,所以随着斜率$k$的减小而增大

这是由单调性的,所以可以根据我们每次的切点在$m$左边还是右边来二分

这样当我们找到$x=m$时,就找到了这个点

一个例题

感性理解,设$g(x)$表示生成树中含有$x$条白边的生成树权值

那么$g(x)$一定是一个下凸函数,因为前面选的白边少,所以有更多黑边的选择空间…

我们尝试用斜率$k$的直接切这个凸包

$b=g(x)-kx$

所以先给每条边减去$k$的权值,然后跑普通的最小生成树得到$b$,记此时的$x$为$res$

下凸壳的斜率是递增的,所以随着$k$的递增切点$x$也是递增的,具备单调性

当$res<need$时,显然$k$往右边二分

当$res>=need$时,$k$往左边二分

这样最后可以二分到$need$处

#include 
   
    using namespace std;const int maxn = 5e6+10;int n,m,ned,fa[maxn],cost;struct edge{
   	int l,r,w,type;	bool operator < ( const edge&tmp )	const	{
   		if( w!=tmp.w )	return w
    
     > n >> m >> ned;	for(int i=1;i<=m;i++)	{
   		cin >> a[i].l >> a[i].r >> a[i].w >> a[i].type;		a[i].l++; a[i].r++;	}	sort( a+1,a+1+m );	int l = -100, r = 100, ans = 0;	while( r>=l )	{
   		int mid = (l+r)/2;		if( isok(mid)>=ned )//二分的点在左边,斜率应该减小			r = mid-1, ans = cost+mid*ned;		else			l = mid+1;		}	cout << ans;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116307738 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！