HDOJ--4791--Alice's Print Service - c++编程基础

题意：现在你要打印一些东西，比如需要99张纸，打印100张以下时话费10元每张，100张及100张以上时需要5元每张，此时你可以选择打印100张，使得花费更小。现给一个数字n，表示n个区间段，然后有s1,p1,s2,p2......sn,pn，表示打印纸张大于等于s1而小于s2时，每张纸话费p1元，现有m个询问，问每次给你x张纸，所需的最小花费是多少。

思路：可以从后往前做一个O（n）的预处理，表示需要的纸张少于si时，多打印纸需要的最小花费。从后往前，则min[ si ] = min ( si*pi , min[ si+1 ] ),之后每次查询只需比较min[si]和正常方法的话费取最小即可。

因为输出量较大 10^6 用cout果断T了，需要用printf

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    using namespace std; #define PI acos(-1.0) #define MAXN 100100 #define eps 1e-7 #define INF 0x7FFFFFFF #define seed 131 //#define long long ll; #define unsigned long long ull; #define lson l,m,rt<<1 #define rson r,m+1,rt<<1|1 long long s[MAXN],p[MAXN]; long long minm[MAXN]; int main(){ long long n, m, i, j; long long t; long long x,ans; scanf("%I64d",&t); while(t--){ scanf("%I64d%I64d",&n,&m); for(i=0;i
                   
                    =0;i--){ long long tt = s[i] * p[i]; minm[i] = min(tt,minm[i+1]); } for(i=0;i