T3 C小田喂猫

思路：

猫粮可以两各部分：

• 在k天内可以吃完；
• 在k天内不能吃完；

用暴力会超时，要用二分，找中间点k；

用前缀和求出k在每个位置得和；

#include
using namespace std;
long long n,q,k,d[1000010],e[1000010];
struct f{
	long long a,b;
} c[1000010];
bool cmp(f x,f y){
	return x.b<y.b;
}
int bs1(){
	int l=1,r=n;
	while(l<r){
		int mid =l+r>>1;
		if(c[mid].b>=k) r=mid;
		else l=mid+1;
	}
	if(c[l].b>=k)return l;
	else return n+1;
}
int main(){	
	cin>>n;
	for(int i=1;i<=n;i++)cin>>c[i].a;
	for(int i=1;i<=n;i++)cin>>c[i].b;
	sort(c+1,c+1+n,cmp);
	for(int i=1;i<=n;i++){
		d[i]=d[i-1]+c[i].a;
	}
	for(int i=1;i<=n;i++)e[i]+=e[i-1]+c[i].a*c[i].b;
	cin>>q;
	while(q--){
		cin>>k;
		int is=bs1();
		cout<<e[is-1]+(d[n]-d[is-1])*k<<endl;;
	}
	return 0;
}

错误点：

输出r和l弄反了； 二分的判断错了；