题解 | #立希喂猫#

我太菜了，只会做后两题

题目大意

有一些物品，每个的数量是 ，价值是 ，每天每种物品能拿一个，求 能得到的最大价值

具体做法

考虑贪心。每天一定会把所有还有剩余的物品全拿一次，所以第 见物品取得次数是 。把 和 放到一个结构体里，按 排序，统计 的前缀和和 的后缀和，每次询问用二分找到一个点 使得 && 输出 即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,sum[100010],summ[100010];
struct node{
	int a,b;
}x[100010];
bool cmp(node a,node b){
	return a.b<b.b;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&x[i].a);
	for(int i=1;i<=n;i++) scanf("%lld",&x[i].b);
	sort(x+1,x+1+n,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i].a*x[i].b;
	for(int i=n;i>=1;i--) summ[i]=summ[i+1]+x[i].a;
	int q;
	scanf("%lld",&q);
	while(q--){
		int k;
		scanf("%lld",&k);
		int l=0,r=n,ans=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(x[mid].b>=k) r=mid-1;
			else ans=mid,l=mid+1;
		}
		printf("%lld\n",sum[ans]+summ[ans+1]*k);
	}
    return 0;
}