HDU4791_Alice's Print Service

全场最水题。

保留打印a[i]份分别需要的钱，从后往前扫一遍，保证取得最优解。

查找的时候，二分同时判断最小值即可。

注意初值的设定应该设定为long long 的无穷大。

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100100
typedef long long ll;
using namespace std;

ll a[maxn],b[maxn],c[maxn],f[maxn],ans,n,m,t,k,num;

ll find(ll x)
{
    if (x>=a[n]) return n;
    if (x<=a[1]) return 1;
    ll l=1,r=n,mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (a[mid]>=x) r=mid;
            else l=mid+1;
    }
    if (x<a[l]) l--;
    return l;
}

int main()
{
    scanf("%I64d",&t);
    while (t--)
    {
        scanf("%I64d%I64d",&n,&m);
        for (ll i=1; i<=n; i++)
        {
            scanf("%I64d%I64d",&a[i],&b[i]);
            c[i]=a[i]*b[i];
        }
        f[n]=c[n];
        f[n+1]=~0U>>1;
        f[n+1]<<=31;
        for (ll i=n-1; i>=1; i--) f[i]=min(f[i+1],c[i]);
        while (m--)
        {
            scanf("%I64d",&num);
            if (num<a[1])
            {
                printf("%I64d
",f[1]);
                continue;
            }
            k=find(num);
            if (k==n)
            {
                printf("%I64d
",num*b[n]);
                continue;
            }
            ans=min(num*b[k],f[k+1]);
            printf("%I64d
",ans);
        }
    }
    return 0;
}