题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4791

题面：

Alice‘s Print Service

1
2 3
0 20 100 10
0 99 100

0
1000
1000

题意：

    打印张数越多价格区间越优惠，（也可能相同）。问给定张数为n的时候，打印多少张最省钱，即虽然打印多了，但是单价低了，故整个价格也就自然低了。问最后花多少钱。

解题：

    先预处理出每个区间的最小花费，即它的临界值乘以单价，然后从小到大排个序。对于每组样例，算出它在本身区间内的花费，然后用二分法（直接用了upper_bound函数）找出小于其花费的最后一个位置P。从0开始遍历最小花费数组，直至P。若遍历过程中发现，有合法区间，即该区间对应张数大于本身张数，则停止遍历，输出当前代价。其实这样写，算是水过的吧（700ms），复杂度比较高了。

    比较好的解法是先预处理出每个区间的最优值，然后每输入一个数，只要找到该数属于哪个区间即可。（minn的意义是指该区间范围内打印临界张数的最优值）预处理过程为 minn[i]=min(minn[i],minn[i+1]); minn[i]的初始值为直接在该区间打印临界张数的代价。i从大到小遍历一遍即可。因为i+1的张数大于i的张数，故minn[i]可以直接取,minn[i+1]的值，又因为minn[i]是从大到小求得，minn[i+1]保存的是即是后面所有的最优值。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <string>
#include <iomanip>
#define LL long long
using namespace std;
struct cost
{
	int num;
	long long minn;
}store[100010];
bool cmp(cost a,cost b)
{
	return a.minn<b.minn;
}
LL mini[100010];
int main()
{
	int storep[100010],stores[100010];
	int t,n,m,p,tmp;
	bool flag;
	LL val;
    scanf("%d",&t);
	while(t--)
	{
      scanf("%d%d",&n,&m);
	  for(int i=0;i<n;i++)
	  {
		  scanf("%d%d",&stores[i],&storep[i]);
		  store[i].num=i;
		  store[i].minn=1LL*storep[i]*stores[i];
	  }
	  sort(store,store+n,cmp);
	  for(int i=0;i<n;i++)
	  {
		  mini[i]=store[i].minn;
	  }
	  for(int i=0;i<m;i++)
	  {
		  scanf("%d",&tmp);
		  if(tmp>=stores[n-1])
		  {
			  printf("%lld\n",1LL*tmp*storep[n-1]);
		  }
		  else
		  {
			  flag=false;
			  p=lower_bound(stores,stores+n,tmp)-stores;
			  //cout<<"storep: "<<storep[p]<<endl;
			  val=1LL*storep[p-1]*tmp;
			 // for(int i=0;i<p+1;i++)
				  //cout<<"price: "<<storep[i]<<endl;
			  //cout<<"val: "<<val<<endl;
			  p=upper_bound(mini,mini+n,val)-mini;
			  for(int i=0;i<p;i++)
			  {
				  if(stores[store[i].num]>=tmp)
				  {
					  flag=true;
					  printf("%lld\n",store[i].minn);
					  break;
				  }
			  }
			  if(!flag)
			  {
				  if(stores[store[p].num]>=tmp&&mini[p]<=val)
				  {
					  flag=true;
					  printf("%lld",store[p].minn);
				  }
			  }
			  if(!flag)
			  {
				  printf("%lld\n",val);
			  }
		  }
	  }

	}
	return 0;
}

HDU 4791 Alice's Print Service

原文：http://blog.csdn.net/david_jett/article/details/46916197