題意：
? ? ? ?給一個終點，然后給你一個卡車距離終點的距離，還有其他個加油站距離終點的距離，然后每走一個單位距離要花費一個單位油，卡車的郵箱是無限大的，而每個加油站的油量是有限的，整個路徑是一個線性的，然后求到達終點的最少加油次數。


思路：?
? ? ? 想了將近20分鐘才想出來，哎！ 我的方法是貪心，大體思路是這樣，先給加油站排序，然后從離自己最緊的開始枚舉，如果當前能到達該加油站，那么把改加油站存起來，如果到達不了，那么就從之前存的里面取一個油量最大的加油，增加了當前能到的最大程度（這個值期初是卡車的原始油量），如果還是到不了，再繼續取，就這樣一直進行到到達終點，或者是改從庫存里面取最大的加油的時候發現庫存沒有加油站了為止，對于這個庫存我是用優先隊列模擬的，這個不固定，用什么都行，比如set，一次操作的時間復雜度都是log(n),最后別忘了兩種特殊情況，就是不用加油直接可以到達終點，還有就是有可能所有加油站都必須加油（這個是小心忘記一個判斷），當然如果寫的好的話無形中就躲開了這兩種易錯點，比如虛擬終點0 0 啥的，就說這么多吧！下面是我的方法，寫的比較挫！而且還很有可能和官方標程思路不一樣，我的時間復雜度是O(n*log(n))的。對了！最后還有兩點，一個是記得給加油站排個序，還有就是不存在比卡車還遠的加油站，一開始想多了。


#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 10000 + 100


using namespace std;


typedef struct
{
? ? int a ,b;
}P;


typedef struct NODE
{
? ? int x;
? ? friend bool operator < (NODE a ,NODE b)
? ? {
? ? ? ? return a.x < b.x;
? ? }
}NODE;


P p[N];


bool camp(P a ,P b)
{
? ? return a.a < b.a;
}


int ?main ()
{
? ? int n ,i ,x ,y;
? ? scanf("%d" ,&n);
? ? for(i = 1 ;i <= n ;i ++)
? ? scanf("%d %d" ,&p[i].a ,&p[i].b);
? ? scanf("%d %d" ,&x ,&y);
? ? sort(p + 1 ,p + n + 1 ,camp);
? ? int nowsum = 0 ,mkok = 0 ,nowlen = y;
? ? if(y >= x) mkok = 1;
? ? priority_queue<NODE>q;
? ? NODE xin ,tou;
? ? while(!mkok && n >= 1)
? ? {
? ? ? ? if(nowlen >= x - p[n].a)
? ? ? ? {
? ? ? ? ? ? xin.x = p[n].b;
? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? n --;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if(q.empty()) break;
? ? ? ? ? ? tou = q.top();
? ? ? ? ? ? q.pop();
? ? ? ? ? ? nowlen += tou.x;
? ? ? ? ? ? nowsum ++;
? ? ? ? ? ? if(nowlen >= x)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mkok = 1;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? while(!mkok && !q.empty())
? ? {
? ? ? ? tou = q.top();
? ? ? ? q.pop();
? ? ? ? nowlen += tou.x;
? ? ? ? nowsum ++;
? ? ? ? if(nowlen >= x)
? ? ? ? {
? ? ? ? ? ? mkok = 1;
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? if(!mkok) nowsum = -1;
? ? printf("%d\n" ,nowsum);
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ2431贪心（最少加油次数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。