程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ--4791--Alice&#39;s Print Service

HDOJ--4791--Alice&#39;s Print Service

編輯：C++入門知識

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
#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