【YbtOJ#20071】礼物购买

题目

题目链接：http://noip.ybtoj.com.cn/problem/20071

思路

记 (sum[i]) 表示按价格从大到小排序之后前 (i) 个物品的价格和。
然后假设当前有 (w) 元，要从第 (i) 个物品开始买，二分出第一个 (j) 使得 (sum[j]-sum[i-1]leq w)，然后将 (isim j) 全部买下，剩余钱买尽量多的 (j+1)。
加下来再次二分出第一个可以买的物品 (i')，继续上述操作即可。
假设我们有 (w) 元后一次操作变成了 (w') 元，当买的最后一个物品价格超过 (frac{w}{2}) 时，(w') 显然不超过 (w-) 价格，所以 (w'<frac{w}{2})；当最后一个物品价格不超过 (frac {w}{2}) 时，因为买了最后一个物品之后买不了下一个物品了，所以剩余的钱一定不超过最后一个物品的价格，也就有 (w'leq frac{w}{2})。
所以上述循环只会进行 (O(log w)) 次，时间复杂度 (O(mlog nlog w))。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100010;
int n,m,ans,cnt[N];
ll w,sum[N],b[N];

struct node
{
	ll v,x;
}a[N];

bool cmp(node x,node y)
{
	return x.v>y.v;
}

int main()
{
	freopen("present.in","r",stdin);
	freopen("present.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&a[i].v,&a[i].x);
		b[i]=a[i].v;
	}
	sort(b+1,b+1+n);
	sort(a+1,a+1+n,cmp);
	for (int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i].x*a[i].v;
		cnt[i]=cnt[i-1]+a[i].x;
	}
	sum[n+1]=b[n+1]=a[n+1].v=1e18;
	while (m--)
	{
		scanf("%lld",&w);
		ans=0;
		for (int i=1;i<=n;)
		{
			int r=upper_bound(sum+1,sum+2+n,sum[i-1]+w)-sum;
			w-=sum[r-1]-sum[i-1]; ans+=cnt[r-1]-cnt[i-1];
			ans+=w/a[r].v; w%=a[r].v;
			i=n-(upper_bound(b+1,b+n-r+1,w)-b-1)+1;
		}
		printf("%d
",ans);
	}
	return 0;
}