首页 > 代码库 > 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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。