鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

Codeforces 635E Package Delivery【贪心】

来源:互联网 作者:佚名 时间:2016-05-12 15:57
题目链接: http://codeforces.com/contest/635/problem/E 题意: 从坐标为0的地方出发到坐标为 d 的终点,初始油箱是满的,途中有若干加油站,坐标为 x i ,每加一个单位的油收 p i 元,油箱最多装n个单位,问到达目的地最少需要多少元。 分析: 之前在poj

题目链接:

http://codeforces.com/contest/635/problem/E

题意:

从坐标为0的地方出发到坐标为d的终点,初始油箱是满的,途中有若干加油站,坐标为xi,每加一个单位的油收pi元,油箱最多装n个单位,问到达目的地最少需要多少元。

分析:

之前在poj做过一个类贪心,是每个加油站油量有限,问最少需要经过多少加油站。
那一道贪心的原则是“直到走不到下一站,再在这个站加油。“
而这道题贪心原则就是“遇到便宜的就先把油加上,避免走到后面加更贵的油“,那么我们怎么保证遇到的是便宜的呢?可以预处理一遍,倒着推一遍,记录每个加油站的后面的最近的比他便宜的,这样到达该加油站只要加到能走到下一个便宜的就好了,然后到达下一个便宜的再加油。。。依次下去,如果某个加油站后面没有比他更小的,那么直接加满,希望能用便宜的油多走一些路。

代码:

#include<cstdio>
#include<stack>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  "
#define pl(x) cout << #x << ": " << x << endl;
#define sa(x) scanf("%d",&(x))
#define sal(x) scanf("%I64d",&(x))
#define xx first
#define yy second
#define mdzz cout<<"mdzz"<<endl;
const int maxn = 2e5 + 5, oo =0x3f3f3f3f;
typedef pair<int, int>p;
typedef long long ll;
int nt[maxn];
p s[maxn];
/*贪心 对于每个位置找最近的最小的,判断距离,选择充多少*/
int main (void)
{
    int d, n, m;sa(d), sa(n), sa(m);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        s[i] =  p(x, y);
    }
    s[0] = p(d, 0);
    s[m + 1] = p(0, oo);
    m += 2;
    sort(s, s + m);
    //倒着推一遍找下一个最小的
    stack<int>q;
    for(int i = m - 1; i >= 0; i--){
        while(!q.empty() && s[i].yy <= s[q.top()].yy) q.pop();
        if(q.empty()) nt[i] = -1;
        else nt[i] = q.top();
        q.push(i);
    }
    ll ans = 0;
    int now = n;//还剩多少
    int add = 0;//要加到多少
    for(int i = 0; i < m; i++){
        if(now < 0) return puts("-1"), 0;
        if(nt[i] == -1){//最小的了,加到走到最后
            add = d - s[i].xx;
        }else add = s[nt[i]].xx - s[i].xx;
        if(add > n) add = n;//最多n
        if(add > now){
            ans += (add - now) * 1ll *  s[i].yy;
            now = add;
        }//选择加油
        now -= s[i + 1].xx - s[i].xx;
    }
    printf("%I64d\n", ans);
    return 0;
}
上一篇:c++作业-5
下一篇:笔试题51. LeetCode OJ (38)
网友评论
<