Gadgets for dollars and pounds
题解
给一个单 \(\log\) 题解。
“求最早完成买 \(k\) 样东西的天数。”——很明显的二分答案。
在检验函数中，我们应当把前 \(k\) 小的物品费用之和与总金额作比较，其它题解大多使用直接排序的方法，于是就多了一只 \(\log\)。其实没有必要，因为总共只有两种物品，我们使用类似归并排序的双指针法，这样只需要在二分的外层 \(O(n\log n)\) 排序，二分内层 \(O(n)\) 归并，总复杂度 \(O(n\log n)\)。
但是这题居然要输出方案，需要记录排序前的位置，实在多少有点恶心。
代码：
/*
* @Author: operator_
* @Date: 2024-02-13 11:40:49
* @Last Modified by: operator_
* @Last Modified time: 2024-02-13 12:12:14
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,m,k,s,v[3][200005],p[3][200005],l[3];
struct QWQ{int v,id;} a[3][200005];
bool cmp(QWQ a1,QWQ a2) {return a1.v<a2.v;}
bool check(int mid) {
int i=0,j=0,sum=0;
while(i+j<k)
if(a[1][i+1].v*v[1][mid]<a[2][j+1].v*v[2][mid])
sum+=a[1][++i].v*v[1][mid];
else sum+=a[2][++j].v*v[2][mid];
return sum<=s;
}
signed main(){
cin>>n>>m>>k>>s;
v[1][0]=v[2][0]=INT_MAX;
for(int i=1;i<=n;i++) {
v[1][i]=rd();
if(v[1][i-1]>v[1][i]) p[1][i]=i;
else p[1][i]=p[1][i-1],v[1][i]=v[1][i-1];
}
for(int i=1;i<=n;i++) {
v[2][i]=rd();
if(v[2][i-1]>v[2][i]) p[2][i]=i;
else p[2][i]=p[2][i-1],v[2][i]=v[2][i-1];
}
p[1][n+1]=p[2][n+1]=n+1;
for(int i=1,t,d;i<=m;i++)
t=rd(),d=rd(),a[t][++l[t]]={d,i};
a[1][++l[1]].v=a[2][++l[2]].v=INT_MAX;
sort(a[1]+1,a[1]+l[1]+1,cmp);sort(a[2]+1,a[2]+l[2]+1,cmp);
int ll=1,rr=n+1,ans=0;
while(ll<=rr) {
int mid=(ll+rr)>>1;
if(!check(mid)) ll=mid+1;
else ans=mid,rr=mid-1;
}
if(ans==n+1) return puts("-1"),0;
cout<<ans<<endl;
int i=0,j=0;
while(i+j<k)
if(a[1][i+1].v*v[1][ans]<a[2][j+1].v*v[2][ans])
printf("%lld %lld\n",a[1][++i].id,p[1][ans]);
else printf("%lld %lld\n",a[2][++j].id,p[2][ans]);
return 0;
}