HDU-5380 Travel with candy(貪心+單調隊列)

Travel with candy

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

Total Submission(s): 396    Accepted Submission(s):

194

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

(N≤2×105,C≤106)

The second line contains N

numbers a1,a2,...,an

. It is guaranteed that ai>ai−1

for each 1<i<=N

.

Next N+1

line : the i-th line contains two numbers buyi−1

and selli−1

respectively. (selli−1≤buyi−1≤106

)

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

Author

SXYZ

Source

​​2015

Multi-University Training Contest 8 ​​

Recommend

wange2014   |   We have carefully selected several

similar problems for you:  ​​6216​​​ ​​6215​​​ ​​6214​​​ ​​6213​​​ ​​6212​​ 

思路：

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

2、其它的部分我們可以帶着準備賣。

那麼每次離開一個點的時候，我們都把口袋補充滿。

那麼每次到達一個點的時候，我們口袋裡都會剩下路途消耗之後的糖果。

此時：

1、口袋裡那些購買價格高于目前點購買價格的糖果，我們可以當它們沒有被買過，直接以買入價賣出就好。

2、口袋裡那些購買價格低于目前點賣出價格的糖果，我們可以當它們有3種用途，第一種是後面被優先消耗了，第二種是在價格更高的點賣出了，第三種是到了最後剩下了。前兩種可以忽視掉目前點，第三種則相當于這些糖果在這個點賣出了。那麼我們就可以看做這些糖果在這個點就被賣出了，那麼它們的買入價就可以看做這個點的賣出價。(意思就是，如果在這個點的後面還存在比目前點更優的情況來賣掉，沒關系，這裡先把賣掉，在用原價把買回來，相當于沒有賣！)

或者換句話說，我買入了一個糖果，它的價值就是買入價，如果我帶着它到了一個賣出價更高的地方，那麼它的價值就成了賣出價。在路上我隻消耗目前價值最低的糖果，如果一個糖果到了最後我都沒有吃的話，那麼就意味着我可以在它價值最高的地方把它賣掉。

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=2e5+5;
 5 int T,n,m;
 6 int a[MAX],b[MAX],c[MAX];
 7 struct Node{int val,num;}q[MAX];
 8 int low,high;
 9 int main(){
10     freopen ("candy.in","r",stdin);
11     freopen ("candy.out","w",stdout);
12     int i,j;
13     scanf("%d",&T);
14     while (T--){
15         scanf("%d%d",&n,&m);n++;
16         a[0]=a[1]=0;
17         for (i=2;i<=n;i++) scanf("%d",a+i);
18         for (i=1;i<=n;i++) scanf("%d%d",b+i,c+i);
19         LL ans=0;
20         int dis,sum=0;
21         low=1,high=0;
22         for (i=1;i<=n;i++){
23             dis=a[i]-a[i-1];sum-=dis;
24             while (dis!=0){
25                 if (q[low].num<=dis){
26                     dis-=q[low].num;
27                     low++;
28                 }
29                 else{
30                     q[low].num-=dis;
31                     dis=0;
32                 }
33             }
34             for (j=low;j<=high;j++)
35                 q[j].val=max(q[j].val,c[i]);
36             while (low<=high && q[high].val>b[i]){
37                 ans-=(LL)q[high].val*(LL)q[high].num;
38                 sum-=q[high].num;
39                 high--;
40             }
41             if (sum<m){
42                 high++;
43                 q[high].val=b[i];q[high].num=m-sum;
44                 ans+=(LL)b[i]*(LL)(m-sum);
45                 sum=m;
46             }
47         }
48         while (low<=high) ans-=(LL)q[low].val*(LL)q[low].num,low++;
49         printf("%lld\n",ans);
50     }
51     return 0;
52