POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。

所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>下的sort函数,对pair<int,int>类型的输入进行排序,非基本类型的数据排序需要重写sort函数的第三个参数。

源代码

#include<queue>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> p;

bool comp(p p1,p p2)
{
    return p1.first<p2.first;
}

int main()
{
    int N,P,L;
    cin>>N;

    vector<p> input;
    int a,b;
    for(int i=N-1;i>=0;i--)
    {
        cin>>a>>b;
        pair<int,int> mm = make_pair(a,b);
        input.push_back(mm);

    }
    cin>>L>>P;

    sort(input.begin(),input.end(),comp);

    int counter=0;
    int go=0;
    priority_queue<int> gas;
    int i=0;
    while(go<L)
    {

        go+=P;
        if(go<L)
        {
            P=0;
            while(!input.empty()&&L-input.back().first<=go)
                {
                    gas.push(input.back().second);
                    input.pop_back();
                    }
                    if(gas.empty())
                        {
                            cout<<-1<<endl;
                            return -1;
                        }
                    P+=gas.top();
                    gas.pop();
                    counter++;

        }

    }
    cout<<counter<<endl;
    return counter;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青青天空树

A除以B问题

描述:本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。

29020
来自专栏CDA数据分析师

excel公式中14种运算符,帮你整理齐了

文 | 赵志东 运算符是公式中最主要的组成部分,包括数学运算符、逻辑运算符和连接运算符等,下面我们就全面学习一下excel公式里的运算符。 一、运算符 1、 数...

21650
来自专栏编程

从机器学习学python(一)——numpy中的shape、tile、argsort

从机器学习学python(一) ——numpy中的shape、tile、argsort (原创内容,转载请注明来源,谢谢) 注:本系列是我在学习机器学习过程中,...

20550
来自专栏calmound

uva Excuses, Excuses!

题意:给几个单词,在给几个句子,输出包含最多单词的那个句子,大小写不分,末尾空行 分析:这道题能A,还是挺开心的,但不说多难,而是又学会了个函数,又知道了个细节...

37750
来自专栏Python爬虫与数据挖掘

浅谈网络爬虫中广度优先算法和代码实现

前几天给大家分享了网络爬虫中深度优先算法的介绍及其代码实现过程,没来得及上车的小伙伴们可以戳这篇文章——浅谈网络爬虫中深度优先算法和简单代码实现。今天小编给大家...

15350
来自专栏Golang语言社区

Go语言 -浮点数

Go提供了两种size的浮点数,float32和float64。它们的算术规范是由IEEE754国际标准定义,现代CPU都实现了这个规范。 浮点数能够表示的范...

41440
来自专栏GIS讲堂

Geotools中实现NC转等值面

前面的文章有实现IDW插值并生成等值面的,本文在前文基础上实现气象NC数据生成等值面。

37440
来自专栏编程之旅

堆排序算法

啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,那么就代表堆排序算法的概念被我忘的差不多了,写...

25730
来自专栏数据结构与算法

P2485 [SDOI2011]计算器

题目描述 你被要求设计一个计算器完成以下三项任务: 1、给定y、z、p,计算y^z mod p 的值; 2、给定y、z、p,计算满足xy ≡z(mod p)的最...

438100
来自专栏Java Web

最大子段和问题

问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

44050

扫码关注云+社区

领取腾讯云代金券