本文主要是介绍HDU 4791 Alice's Print Service 注意一点就好,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:打印纸,你打印的纸的总价钱,纸张数不同,他所要的钱不同,问你打印一定的纸张怎样更加的省钱。之间的关系看题目里的表达式。
想法:看是我一下就想到了,有两种可能,一种是当前的纸张数乘以这个范围的小的那个端点的值,还有一种是大的那个端点值乘以他的那个范围的个数取最小。
这样的想法是对的,但是我没有考虑到还有后面的乘积可能会更小,所以这里要处理一下,还有就是查找的时候用二分,不然会超时。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+5;
int n,m;
__int64 s[N*2],p[N*2],bro[N*2];
int find(__int64 x)
{int low=1,up=n,ans;if(x>=s[n]) return n;while(low<=up){int mid=(low+up)/2;if(x>=s[mid]){ans=mid;low=mid+1;}else up=mid-1;}return ans;
}
void Input()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%I64d%I64d",&s[i],&p[i]); }bro[n]=s[n]*p[n];for(int i=n-1;i>=1;i--){__int64 k=s[i]*p[i];bro[i]=bro[i+1]<k?bro[i+1]:k;}for(int i=1;i<=m;i++){__int64 num;scanf("%I64d",&num);int id=find(num);if(id==n){printf("%I64d\n",p[n]*num);continue;}__int64 res1=num*p[id];__int64 res2=bro[id+1];res1=res1>res2?res2:res1;printf("%I64d\n",res1);}
}
int main()
{int t;scanf("%d",&t);while(t--){Input();}return 0;
}
这篇关于HDU 4791 Alice's Print Service 注意一点就好的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!