# HDU 5380 Travel with candy （单一队列&贪心）

www.MyException.Cn  网友分享于：2015-08-17  浏览：0次
HDU 5380 Travel with candy （单调队列&贪心）

# Travel with candy

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description
There are n+1 cities on a line. They are labeled from city 0 to city n. Mph has to start his travel from city 0, passing city 1,2,3...n-1 in order and finally arrive city n. The distance between city i and city 0 is ai. Mph loves candies and when he travels one unit of distance, he should eat one unit of candy. Luckily, there are candy shops in the city and there are infinite candies in these shops. The price of buying and selling candies in city i is buyi and selli per unit respectively. Mph can carry at most C unit of candies.
Now, Mph want you to calculate the minimum cost in his travel plan.

Input
There are multiple test cases.
The first line has a number T, representing the number of test cases.
For each test :
The first line contains two numbers N and C (N2×105,C106)
The second line contains N numbers a1,a2,...,an. It is guaranteed that ai>ai1 for each 1<i<=N .
Next N+1 line : the i-th line contains two numbers buyi1 and selli1 respectively. (selli1buyi1106)

The sum of N in each test is less than 3×105.

Output
Each test case outputs a single number representing your answer.(Note: the answer can be a negative number)

Sample Input
1
4 9
6 7 13 18
10 7
8 4
3 2
5 4
5 4

Sample Output
105

1、在路上消耗的糖果一定是尽量最便宜的。

2、其它的部分我们可以带着准备卖。

1、口袋里那些购买价格高于当前点购买价格的糖果，我们可以当它们没有被买过，直接以买入价卖出就好。

2、口袋里那些购买价格低于当前点卖出价格的糖果，我们可以当它们有3种用途，第一种是后面被优先消耗了，第二种是在价格更高的点卖出了，第三种是到了最后剩下了。前两种可以忽视掉当前点，第三种则相当于这些糖果在这个点卖出了。那么我们就可以看做这些糖果在这个点就被卖出了，那么它们的买入价就可以看做这个点的卖出价。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#define moo 1000000007//10^9+7
#define PI acos(-1.0)
#define eps 1e-5
using namespace std;
struct City
{
int dis;
int sel;
}a[200005];
struct Queue
{
int num;
int val;
}que[200005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
a[0].dis=a[1].dis=0;
for(int i=2;i<=n+1;i++)
scanf("%d",&a[i].dis);
for(int i=1;i<=n+1;i++)
//以1号点为起点，n+1号点为终点，0号点的距离置0是为了起点不用单独拿出来讨论，节约代码。
long long ans=0;
int he=0;
int en=0;//单调队列维护口袋里的糖果。
int sum=0;//存的当前口袋里的糖果总量
for(int i=1;i<=n+1;i++)
{
int dis=a[i].dis-a[i-1].dis;
sum-=dis;//每到一个点，首先消耗dis个
while(dis!=0)
{
if(que[he+1].num<=dis)
{
dis-=que[he+1].num;
he++;
}
else
{
que[he+1].num-=dis;
dis=0;
}
}//从队列头开始吃掉dis个糖果

//将口袋里价值低于当前点出售价格的糖果价值更新为当前点的出售价格
for(int j=he+1;j<=en;j++)
if(que[j].val<a[i].sel)
que[j].val=a[i].sel;

//将口袋里价值高于当前点购买价格的糖果按它们最高价值卖掉。
{
ans-=(long long)que[en].val*que[en].num;
sum-=que[en].num;
en--;
}

//离开该点前，将口袋补充满
if(sum!=m)
{
en++;
que[en].num=m-sum;
ans+=(long long)que[en].num*que[en].val;
sum=m;
}
}
//将最后剩下的糖果按照它们的最高价值卖掉
while(he!=en)
{
ans-=(long long)que[he+1].num*que[he+1].val;
he++;
}
cout<<ans<<endl;
}
return 0;
}