2015
09-18

# Alice’s Print Service

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1596    Accepted Submission(s): 380

Problem Description
Alice is providing print service, while the pricing doesn’t seem to be reasonable, so people using her print service found some tricks to save money.
For example, the price when printing less than 100 pages is 20 cents per page, but when printing not less than 100 pages, you just need to pay only 10 cents per page. It’s easy to figure out that if you want to print 99 pages, the best choice is to print an
extra blank page so that the money you need to pay is 100 × 10 cents instead of 99 × 20 cents.
Now given the description of pricing strategy and some queries, your task is to figure out the best ways to complete those queries in order to save money.

Input
The first line contains an integer T (≈ 10) which is the number of test cases. Then T cases follow.
Each case contains 3 lines. The first line contains two integers n, m (0 < n, m ≤ 105 ). The second line contains 2n integers s1, p1 , s2, p2 , …, sn, pn (0=s1 < s2
< … < sn ≤ 109 , 109 ≥ p1 ≥ p2 ≥ … ≥ pn ≥ 0).. The price when printing no less than si but less than si+1 pages is pi cents per page (for i=1..n-1). The
price when printing no less than sn pages is pn cents per page. The third line containing m integers q1 .. qm (0 ≤ qi ≤ 109 ) are the queries.

Output
For each query qi, you should output the minimum amount of money (in cents) to pay if you want to print qi pages, one output in one line.

Sample Input
1
2 3
0 20 100 10
0 99 100

Sample Output
0
1000
1000

Source

打印张数越多价格区间越优惠，（也可能相同）。问给定张数为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;
}

1. 那妹子所说的话正是我所期待的，，但是生活所迫，拿得起，放不下。现在生活不算艰苦也不算富裕，但是一旦有松懈，就是穷困潦倒了。金钱名利我不想追求太多，但是总得给身边人一份保障是不是？有几个人可以无牵无挂，更何况婚后两家变一家，更加没法无牵无挂了。想想当初有很

2. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

3. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

4. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

5. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

6. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

7. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

8. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

9. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

10. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

11. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…

12. 不想改变你的看法和态度，你依旧可以认为“共济会”是邪恶的，但你实现“人类光明美好未来”的前提就是：将这批人彻底从地球上铲除掉~希望这种“邪恶标签”不会出现在任何人身上，因为后果很可怕…