首页 > 代码库 > HDOJ--4791--Alice's Print Service

HDOJ--4791--Alice's Print Service

题意:现在你要打印一些东西,比如需要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<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
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<n;i++){
            scanf("%I64d%I64d",&s[i],&p[i]);
        }
        minm[n-1] = s[n-1] * p[n-1];
        for(i=n-2;i>=0;i--){
            long long tt = s[i] * p[i];
            minm[i] = min(tt,minm[i+1]);
        }
        for(i=0;i<m;i++){
            scanf("%I64d",&x);
            int pp = upper_bound(s,s+n,x)-s;
            pp--;
            if(pp==n-1){
                ans = x * p[n-1];
            }
            else
                ans = min(minm[pp+1],x*p[pp]);
            printf("%I64d\n",ans);
        }
    }
    return 0;
}


/*
1
2 100
0 20 100 10


999
3 100
0 20 100 10 1000 2
*/