Merchant

\(get\)二分新用法。

每道题都有答案范围提示，以前只是以为是用来提示用什么类型输出的。

从来没想过直接用它来二分。

这道题真的刷新了我的认知啊。。。。。。

整道题的复杂度是\(O(nlog1e9)\)。

具体做法是，先\(check\)一下0时刻满不满足要求，如果不满足再进行二分。

关于他为什么可以二分：

可以知道，价值是时间的一次函数，对于任意一个选中的物品的集合，我们将他们\(k、b\)加和，就可以得到对应的斜率与截距，并且，我们只关心同一个\(t\)下的最大值，画出图像，可以发现他是单调增/单调减/单谷函数。

两种单调函数显然可以二分。

单谷函数当左边可以满足要求时，一定会在\(check0\)时就得出答案。

能够二分时，满足要求的点一定在右边，所以当\(check\)为\(false\)时，直接缩下界即可。

进行\(check\)时先用二分到的\(t\)计算出价值，然后将前\(m\)个最大的加和，看是不是大于\(s\)。

Code

#include<bits/stdc++.h>

using namespace std;

namespace STD

{

	#define rr register

	typedef long long ll;

	const int N=1e6+4;

	ll n,m,s;

	ll w[N];

	struct node{ll k,b;}a[N];

	ll read()

	{

		rr ll x_read=0,y_read=1;

		rr char c_read=getchar();

		while(c_read<'0'||c_read>'9')

		{

			if(c_read=='-') y_read=-1;

			c_read=getchar();

		}

		while(c_read<='9'&&c_read>='0')

		{

			x_read=(x_read<<3)+(x_read<<1)+(c_read^48);

			c_read=getchar();

		}

		return x_read*y_read;

	}

	bool cmp(const ll a_,const ll b_){return a_>b_;}

	bool check(int t)

	{

		for(rr int i=1;i<=n;i++)

			w[i]=a[i].k*t+a[i].b;

		nth_element(w+1,w+1+m,w+1+n,cmp);

		ll sum=0;

		for(rr int i=1;i<=m;i++)

		{

			if(w[i]<0) continue;

			if(sum+w[i]>=s) return 1;

			sum+=w[i];

		}

		return 0;

	}

};

using namespace STD;

int main()

{

	n=read(),m=read(),s=read();

	for(rr int i=1;i<=n;i++)

		a[i].k=read(),a[i].b=read();

	if(check(0))

	{

		cout<<0<<'\n';

		return 0;

	}

	int l=1,r=1e9;

	while(l<r)

	{

		int mid=(l+r)>>1;

		if(!check(mid)) l=mid+1;

		else r=mid;

	}

	printf("%d\n",l);

}

2021-08-09 20:34:26 星期一

巴特西

Merchant

最新文章

热门文章