hdu4791水题

题意:

打印东西,给你区间和每个区间的价格,然后输入任务张数,输出最少花费..

题解:

昨晚的小测试就有这个题目,当时蒙B了,怎么也读不懂题目,一直纠结怎么把150拆成100 + 50,有的同学还说是什么dp什么的,吓的我尿了,难题? 后来回去想了下,dp毛线,就是个水题,题目中有一个条件很关键,就是范围越来越大,单价越来越低,所以直接开一个数组,min[a]记录打印a张的最少钱,a是范围的每一个边界点,min[a] = minn(fw[i] * dj[i] ,min[a+1]);
fw 范围 dj 单价;因为越往后范围越大,现在的肯定可以用后面的买,当每一次询问的时候直接用二分找到他在那个范围,如果是最后一个范围直接输出 fw[n] * dj[n],否则输出minn(fw[i] * dj[i] ,min[i+1]) ,哎 ! 水题水不过啊,感觉水题都tm不会做了,这方面必须好好练习.;

#include<stdio.h>

#define N 100000 + 10000



__int64 fw[N];

__int64 dj[N];

__int64 min[N];

__int64 minn(__int64 a ,__int64 b)

{

   return a < b ? a : b;

}

int main ()

{

   int n ,m ,i ,j ,t;

   scanf("%d" ,&t);

   while(t--)

   {

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

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

      {

         scanf("%I64d %I64d" ,&fw[i] ,&dj[i]);

      }

      min[n] = fw[n] * dj[n];

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

      {

         min[i] = minn(min[i+1] ,dj[i] * fw[i]);

      }

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

      {

         __int64 q;

         scanf("%I64d" ,&q);

         __int64 low ,up ,mid;

         low = 1 ,up = n;

         int mk;

         while(low <= up)

         {

             mid = (low + up) / 2;

             if(q >= fw[mid])

             {

                  low = mid + 1;

                  mk = mid;

             }

             else

             up = mid - 1;

          }

          //printf("%d\n" ,mk);

         __int64 ans;

         if(mk != n)

         printf("%I64d\n" ,minn(q * dj[mk] ,min[mk + 1]));

         else

         printf("%I64d\n" ,q * dj[mk]);

      }

   }

   return 0;

}

巴特西

hdu4791水题

最新文章

热门文章