学步园

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3726

题意容易理解：就是一个打印分段收费政策，印的越多，单张价格越低，输入需要印刷的数量，求最小印刷费用

思路：由于印的张数越多，单价越便宜

可以对数据进行预处理：

先求每一种价格对应的最小费用，也就是张数刚刚好时的费用，最小费用sp=s[i]*p[i]；

然后求大于每一个基础数量s[i]后面的所有对应最小费用，用mini[i]保存。

这样对于每组输入，只要对比印刷张数刚刚够的价格和s[i】后的最小价格，取小者就是答案。

附上AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
long long mini[100005];
long long s[100005],p[100005],sp[100005];
int main()
{
    int t,i,j,m,n;
    long long mi,pa,ans,pri;
    long long id;
    scanf("%d",&t);
    while(t--)
    {
        memset(s,0,sizeof(s));
        memset(sp,0,sizeof(sp));
        memset(p,0,sizeof(p));
        scanf("%d %d",&n,&m);
        for(i=1; i<=n; i++)
        {
            scanf("%lld %lld",&s[i],&p[i]);
        }
        mi=sp[n]=s[n]*p[n];
        for(i=n-1; i>=1; i--)
        {
            sp[i+1]=s[i+1]*p[i+1];
            if(sp[i+1]<mi)
            {
                mini[i]=sp[i+1];
                mi=sp[i+1];
            }
            else mini[i]=mi;
        }
        for(i=0; i<m; i++)
        {
            scanf("%lld",&pa);
            id=upper_bound(s+1,s+n+1,pa)-s;
            if(id==n+1)
            {
                printf("%lld\n",pa*p[n]);
                continue;
            }
            if(id==1) ;
            else id=id-1;
            pri=p[id]*pa;
            if(pri>mini[id]) ans=mini[id];
            else ans=pri;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

提示：：本人很少写结题报告，表达能力有限，，代码也烂有不对的欢迎指出