本文共 967 字，大约阅读时间需要 3 分钟。

ZOJ - 3726  

题目大意：

      你需要打印纸张，打印店的服务是按张数分档计费的，例如100张以内一张20分，100张以上一张10分；当你需要打印90张时，90*20=1800，此时还不如多打印10张凑成100，这样的花费是100*10=1000。

     现在告诉你打印店的分档计费策略和需要打印的张数，求出最少花费是多少。

题解：

     一道不算很水的签到题，打训练赛的时候一度被它卡了一下。

      先预处理一下，当前档和下一档的最小值比，如果比他大就用下一档(倒着处理，因为有可能隔着好几档都是最小的，如101 10，105 5)

     在找给出的张数属于哪一档时用二分。

#include
   
    #include
    
     using namespace std;#define ll long long#define INF 1e18ll minn[100010];ll s[100010];ll p[100010];int main(){    //freopen("input.txt","r",stdin);    int T,n,m;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        for(int i=1;i<=n;++i)            scanf("%lld%lld",&s[i],&p[i]);        minn[n]=s[n]*p[n];        for(int i=n-1;i>=1;--i)            minn[i]=min(minn[i+1],s[i]*p[i]);        ll ans,x;        int pos;        minn[n+1]=INF;        while(m--)        {            scanf("%lld",&x);            pos=lower_bound(s+1,s+n+1,x)-s;            ans=min(x*p[pos-1],minn[pos]);            printf("%lld\n",ans);        }    }    return 0;}
    
   

转载地址：http://okfgf.baihongyu.com/