HDU-4791-Alice‘s Print Service

分析：

1.由于价格是递减的，所以可能出现si*pi>sj*pj(j>i)。所以要有一个数组来储存当前端点的最小值。

2.然后二分查找当前的si，比较q*p[i]和M[i+1].不过在这之前要确认i是小于n的。】

3.upper_bound是返回第一个大于当前值得坐标，否则返回左闭右开的右端点。而lower_bound是返回第一个大于等于当前值得坐标。所以这里采用upper_bound。

 #include <iostream>

 #include <cstdio>

 #include <math.h>

 #include <algorithm>

 using namespace std;

 #define M 100010

 #define ll long long

 ll s[M],p[M],q[M];

 ll n,m;

 ll best[M];

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int i=;i<T;i++)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)

         {

             scanf("%lld%lld",&s[i],&p[i]);

         }

         ll Min = s[n]*p[n];

         best[n] = Min;

         for(int i =n-;i>=;i--)

         {

             Min = min(Min,s[i]*p[i]);

             best[i] = Min;

         }

         for(int i=;i<=m;i++)

         {

             scanf("%lld",&q[i]);

         }

         for(int i=;i<=m;i++)

         {

             if(q[i]>=s[n])

             {

                 printf("%lld\n",q[i]*p[n]);

                 continue;

             }

             int t = upper_bound(s+,s++n,q[i])-s-;

             printf("%lld\n",min(best[t+],q[i]*p[t]));

         }

     }

     return ;

 }

巴特西

HDU-4791-Alice‘s Print Service

最新文章

热门文章