CodeForces 609D Gadgets for dollars and pounds

二分天数+验证

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=200000+10;
int n,m,k;
long long s;
long long a[maxn],b[maxn],c[maxn];
int t[maxn];
long long A[maxn],B[maxn];
int preA[maxn],preB[maxn];
struct Tmp
{
    int id;
    long long val;
    int day;
} tmp[maxn];

bool cmp(const Tmp&a,const Tmp&b)
{
    return a.val<b.val;
}

int main()
{
    scanf("%d%d%d%lld",&n,&m,&k,&s);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
    for(int i=1; i<=n; i++) scanf("%lld",&b[i]);
    for(int i=1; i<=m; i++) scanf("%d%lld",&t[i],&c[i]);

    A[1]=a[1];
    preA[1]=1;
    for(int i=2; i<=n; i++)
    {
        A[i]=min(A[i-1],a[i]);
        if(A[i-1]<=a[i]) preA[i]=preA[i-1];
        else preA[i]=i;
    }

    B[1]=b[1];
    preB[1]=1;
    for(int i=2; i<=n; i++)
    {
        B[i]=min(B[i-1],b[i]);
        if(B[i-1]<=b[i]) preB[i]=preB[i-1];
        else preB[i]=i;
    }

    int l=1,r=n;
    int mid;
    int ansDay=-1;
    while(l<=r)
    {
        mid=(l+r)/2;
        for(int i=1; i<=m; i++)
        {
            tmp[i].id=i;
            if(t[i]==1) tmp[i].val=A[mid]*c[i];
            else tmp[i].val=B[mid]*c[i];
        }
        sort(tmp+1,tmp+1+m,cmp);
        long long sum=0;
        for(int i=1; i<=k; i++) sum=sum+tmp[i].val;
        if(sum<=s)
        {
            ansDay=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d
",ansDay);
    if(ansDay!=-1)
    {
        for(int i=1; i<=m; i++)
        {
            tmp[i].id=i;
            if(t[i]==1) tmp[i].val=A[mid]*c[i];
            else tmp[i].val=B[mid]*c[i];

            if(t[i]==1) tmp[i].day=preA[ansDay];
            else tmp[i].day=preB[ansDay];
        }
        sort(tmp+1,tmp+1+m,cmp);
        for(int i=1; i<=k; i++)
            printf("%d %d
",tmp[i].id,tmp[i].day);
    }
    return 0;
}