POJ 2431 Expedition（优先队列+贪心)

Related: LeetCode 134 - Gas Station
http://poj.org/problem?id=2431
题目大意：
你需要驾驶一辆卡车行驶L距离，最开始时，卡车上有P的汽油，卡车每开1单位距离需要消耗1单位的汽油。在途中有N个加油站，第i个加油站在距离起点Ai距离的地方，最多可以给卡车加Bi汽油，假设卡车的容量是无限大的，无论加多少油都没有问题。求卡车到达终点需要加的最少的汽油。
思路：
可以换个思路：在到达加油站i时，就获得了一次在之后的任何时候都可以加Bi单位汽油的权利。而在之后需要加油的时候，就认为是在之前经过的加油站加的油就可以。
所以，我们每次没油的时候，选择一个加油站（之前经过的）最大可加油的进行加油（故用堆/优先队列维护）。
A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck now leaks one unit of fuel every unit of distance it travels. 

To repair the truck, the cows need to drive to the nearest town (no more than 1,000,000 units distant) down a long, winding road. On this road, between the town and the current location of the truck, there are N (1 <= N <= 10,000) fuel stops where the cows can stop to acquire additional fuel (1..100 units at each stop). 

The jungle is a dangerous place for humans and is especially dangerous for cows. Therefore, the cows want to make the minimum possible number of stops for fuel on the way to the town. Fortunately, the capacity of the fuel tank on their truck is so large that there is effectively no limit to the amount of fuel it can hold. The truck is currently L units away from the town and has P units of fuel (1 <= P <= 1,000,000). 

Determine the minimum number of stops needed to reach the town, or if the cows cannot reach the town at all. 
http://www.cnblogs.com/stdio/archive/2012/09/26/Chango.html
假设他们的车可以瞬间移动到之前到达过段任意加油站加油。显然，将油用光顺移回到加油站加油再顺移回来和直接经过加油站的时候加油，并且走到没有由从结果上来说时完全等价。

我们的策略是每次走到用光油，在瞬移回一下之前经过段加油站中油最多的地方加油，继续往前走，用光继续瞬移找经过的剩下的油最多段地方加油……直到到达城市，或将可加油全部加满也到达不了下一个加油站为止（这时返回-1）。

贪心性质证明：

设S{1,2,3…n}是所有加油站的集合，r为油箱中剩余油量，d为总路程。A{a1,a2,a3…am}是最优解。T{t1,t2…}是我们用贪心法得到的解，并按贪心的取解顺序排列（即）现证贪心解也是最优解。

若r≥d：则完全不需要加油，贪心法与最优解一样为空集。

若r < d：对i=1：若车在前r个单位的路上未加油，则必会停在离起点r处，无法到达。所以车必在前r的某个加油站加油。取A中在前r单位油量最大的加油站，不妨设为a1。又因为t1为前r路油量最大的加油站，所以有a1≤t1。易(A-{a1})U{t1}即A1{t1,a2,a3…am}也是最优解。

现假设对i=k(k<m)，存在最优解Ak{t1,t2…tk,ak+1,ak+2…am}，则当i=k+1时：若车在前r+t1+t2+..tk个单位的路上只加了k次油，那车最多只能停在离起点r+t1+t2+..tk处，无法到达(k<m若能到达，则与A是最优解矛盾)，所以车在前r+t1+t2+..tk必须至少在加一次油，设取集合{ak+1,ak+2…am}在前r+t1+t2+..tk个单位的路上油量最大的加油站，不妨设为ak+1，因为tk+1是前r+t1+t2+..tk路程上除了t1到tk外最大的加油站，所以ak+1≤tk+1。所以Ak+1{t1,t2..tk+1,ak+2…,am}也是最优解。

综上，由数学归纳法，Am{t1,t2…tm}也是最优解，Am即为贪心解T。

证毕。

1. struct point  
2. {  
3.     int dis;  
4.     int val;  
5.     bool operator<(const point&a)const{  
6.         return val < a.val;  
7.     }  
8. }a[MAXN];  
9. bool cmp(const point &a,const point &b){  
10.     return a.dis<b.dis;  
11. }  
12. int main()  
13. {  
14.     int n,p,L;    
15.     while(~scanf("%d",&n))  
16.     {  
17.         for(int i=1;i<=n;i++)  
18.             scanf("%d%d",&a[i].dis,&a[i].val);  
19.       
20.         scanf("%d%d",&L,&p);  
21.         for(int i=1;i<=n;i++)  
22.             a[i].dis=L-a[i].dis;  
23.         a[++n].dis=L;  
24.         a[0].dis=0;  
25.         sort(a,a+n,cmp);  
26.         priority_queue<point> q;  
27.         int cnt=0;  
28.         for(int i=1;i<=n;i++)  
29.         {  
30.             int d=a[i].dis-a[i-1].dis;  
31.             while(d > p)  
32.             {  
33.                 if(q.empty())  
34.                 {  
35.                     printf("-1\n");  
36.                     goto end;  
37.                 }  
38.                 p+=q.top().val;  
39.                 q.pop();  
40.                 cnt++;  
41.             }  
42.             p-=d;  
43.             q.push(a[i]);  
44.         }  
45.         printf("%d\n",cnt);  
46. end:;  
47.     }  
48.     return 0;  
49. } 

Read full article from POJ 2431 Expedition （优先队列+贪心） - 细语呢喃 - 博客频道 - CSDN.NET