MyException - 我的异常网
当前位置:我的异常网» 综合 » HDU 5380 Travel with candy (单一队列&贪心)

HDU 5380 Travel with candy (单一队列&贪心)

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

本文纯属原创,转载请注明出处。http://blog.csdn.net/zip_fan,谢谢。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5380。

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
 

题意:一条直线上从左至右依次排着0-n号一共n+1个城市,XX要从第0个城市到第n个城市去。现在告诉每个城市到第0号城市的距离。已知XX每走一单位长度的距离就会吃掉一颗糖,XX身上最多带m颗糖,每个城市都有糖果店,XX可以在路上根据当前城市的糖果店的买入卖出价格进行补充口袋和卖出糖果赚钱。那么现在问题来了,它这么从0点走到n点,不走回头路,最少要花费多少钱?(如果最后赚钱了,输出就是负的)

出题人保证了m大于等于任意两个相邻的城市之间的距离。


思路:

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 buy;
    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++)
            scanf("%d%d",&a[i].buy,&a[i].sel);
        //以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;

            //将口袋里价值高于当前点购买价格的糖果按它们最高价值卖掉。
            while(en>he&&que[en].val>a[i].buy)
            {
                ans-=(long long)que[en].val*que[en].num;
                sum-=que[en].num;
                en--;
            }
            
            //离开该点前,将口袋补充满
            if(sum!=m)
            {
                en++;
                que[en].num=m-sum;
                que[en].val=a[i].buy;
                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;
}



版权声明:本文为博主原创文章,未经博主允许不得转载。

文章评论

一个程序员的时间管理
一个程序员的时间管理
10个调试和排错的小建议
10个调试和排错的小建议
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
那些争议最大的编程观点
那些争议最大的编程观点
程序员和编码员之间的区别
程序员和编码员之间的区别
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
 程序员的样子
程序员的样子
旅行,写作,编程
旅行,写作,编程
代码女神横空出世
代码女神横空出世
每天工作4小时的程序员
每天工作4小时的程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
我是如何打败拖延症的
我是如何打败拖延症的
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员的鄙视链
程序员的鄙视链
中美印日四国程序员比较
中美印日四国程序员比较
老程序员的下场
老程序员的下场
总结2014中国互联网十大段子
总结2014中国互联网十大段子
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
鲜为人知的编程真相
鲜为人知的编程真相
我的丈夫是个程序员
我的丈夫是个程序员
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
如何成为一名黑客
如何成为一名黑客
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Java程序员必看电影
Java程序员必看电影
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
漫画:程序员的工作
漫画:程序员的工作
程序员都该阅读的书
程序员都该阅读的书
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
编程语言是女人
编程语言是女人
程序员必看的十大电影
程序员必看的十大电影
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
为什么程序员都是夜猫子
为什么程序员都是夜猫子
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有