CF609D题解

ncwzdlsd · 2023-10-28 13:45:08 · 题解

观察到如果第 x 天可以买完 k 件物品，第 x+1 天也可以，此问题具有决策单调性。

考虑二分最少需要的天数 x。对于当前二分到的天数，找到当前的最小汇率，计算最少需要的花费钱数，与 s 进行比较判断是否可行即可。

代码如下：

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

const int maxn=2e5+5;
int a[maxn],b[maxn],s,m,n,k;
struct node{int t/*type*/,c/*cost*/,id;ll v;}p[maxn];
struct nod{int d,q;}out[maxn];

bool cmp(node a,node b){return a.v<b.v;}

bool check(int x)
{
    int mina=INT_MAX,minb=INT_MAX,d1=1,d2=1;
    for(int i=1;i<=x;i++)
    {
        if(a[i]<mina) mina=a[i],d1=i;
        if(b[i]<minb) minb=b[i],d2=i;
    }
    for(int i=1;i<=m;i++) 
    {
        if(p[i].t==1) p[i].v=p[i].c*mina;
        else p[i].v=p[i].c*minb;
    }
    sort(p+1,p+m+1,cmp);
    ll sum=0;
    for(int i=1;i<=k;i++) sum+=p[i].v;
    if(sum>s) return 0;
    for(int i=1;i<=k;i++)
    {
        out[i].q=p[i].id;
        if(p[i].t==1) out[i].d=d1;
        else out[i].d=d2;
    }
    return 1;
}

signed main()
{
    cin>>n>>m>>k>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=m;i++) cin>>p[i].t>>p[i].c,p[i].id=i;
    int l=0,r=n,ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans) 
    {
        cout<<ans<<'\n';
        for(int i=1;i<=k;i++) cout<<out[i].q<<' '<<out[i].d<<'\n';
    }
    else cout<<"-1";
    return 0;
}