这几天遇到三道相似的贪心问题。
1. 汽车加油问题（算法设计与分析基础 习题4-9）
初始时油量为n。从起点到终点之间有k个加油站，汽车油箱容量上限为n，每个加油站可无限量供应汽油。
给出n,k和相对位置（在一条直线上），求最少加油次数及对应加油记录。
贪心策略：一直走，当到不了站点 i 时，在i-1加油至容量上限n（距离超过n时无解）。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 const int MAX_N=100; 5 int vis[MAX_N]; 6 7 int greedy(int n,int k,int* dis) 8 { 9 memset(vis,0,sizeof(vis)); 10 int ans=0; 11 int cur_petrol=0; 12 for(int i=0;i<=k;i++)//遍历从第一个加油站到终点 13 { 14 cur_petrol-=dis[i];//到达此点后的剩余油量 15 if(cur_petrol<0)//需要在上一点加油了 16 { 17 cur_petrol=n-dis[i];//在上一点加满油后到达这一点后的剩余油量 18 if(cur_petrol<0) return -1;//距离超过油箱容量，无解 19 vis[i]=1; 20 ans++; 21 } 22 } 23 return ans; 24 } 25 26 void print_greedy(int k) 27 { 28 for(int i=1;i<=k;i++)//在0号点（起点）加油不计入 29 { 30 if(vis[i]) printf("%d ", i); 31 } 32 printf("\n"); 33 return ; 34 } 35 36 int main() 37 { 38 freopen("add_petrol.txt","r",stdin); 39 int n,k; 40 int dis[MAX_N]; 41 scanf("%d%d",&n,&k); 42 for(int i=0;i<=k;i++) 43 scanf("%d",&dis[i]);//dis[k]表示第k个驿站到第k+1个的距离 44 int ans=greedy(n,k,dis); 45 if(ans==-1) printf("no solution\n"); 46 else print_greedy(k); 47 return 0; 48 }
贪心策略证明思路：最优值唯一，任意最优解可通过交换元素（保证能够到达终点）改造为贪心选择策略得到的解，其值仍为最优值。（Exchange arguments）
2. Expedition(POJ 2431)
初始时油量为P。从起点到终点之间有k个加油站，汽车油箱容量无上限，每个加油站i能供应的汽油量有上限fi。
给出P,k,相对位置和f数组，求最少的加油次数。
换个角度看：在到达加油站 i 时，就获得了一次在之后任何时候都可以加fi单位汽油的机会。（来自《挑战程序设计竞赛》）
贪心策略：一直走，当到不了站点 i 时，选 i 之前没有加过油的、fj最大的站点j，加上fj量的汽油。（距离超过i之前的全部fj之和时无解）。
为了快速选出前i个加油站fi最大的那个，可用堆来维护。因为上一个问题每个站点是无限量供应汽油，且每次加油的上限量都是相同的，所以不用选择。
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 using namespace std; 5 int n,L,P; 6 struct Stop 7 { 8 int dis,fuel; 9 }stops[10002]; 10 11 bool mycmp(const Stop &a,const Stop &b) 12 { 13 return a.dis<=b.dis; 14 } 15 16 int main() 17 { 18 freopen("2431.txt","r",stdin); 19 scanf("%d",&n); 20 for(int i=1;i<=n;i++) 21 scanf("%d%d",&stops[i].dis,&stops[i].fuel); 22 scanf("%d%d",&L,&P); 23 for(int i=1;i<=n;i++) 24 stops[i].dis=L-stops[i].dis; 25 stops[n+1].dis=L; 26 stops[n+1].fuel=0; 27 stops[0].dis=0; 28 sort(stops+1,stops+1+n+1,mycmp);//按位置排序 29 30 priority_queue<int> q; 31 int cur_fuel=P,cnt=0,flag=0; 32 for(int i=1;i<=n;i++) 33 { 34 cur_fuel-=stops[i].dis-stops[i-1].dis;//到达此点后剩余的油量 35 while(cur_fuel<0)//需要在之前加油才能到这一点 36 { 37 if(q.empty()) {flag=1; break;}//当前i个点都被加过了，无解 38 cur_fuel+=q.top(); 39 q.pop(); 40 cnt++; 41 } 42 q.push(stops[i].fuel); 43 } 44 if(flag) printf("-1\n"); 45 else printf("%d\n",cnt); 46 return 0; 47 }
贪心策略证明思路：最优值唯一，贪心选择策略得到的解至少能达到和其他最优解一样的效果（能够到达终点），其值仍为最优值。（Staying ahead）
3. Duff and Meat(CF588A(#326div2A))
要想愉快地度过第i天，需要吃掉ai kg的肉；当天肉的售价为$pi/kg，无限量供应。要求保持连续n天每天都能吃到ai kg的肉（可以吃之前买来储存的，永远不会过期。。。相当于储存容量无上限）。
给出n和a,p数组，求最少的买肉花费。
参照上一题，这道同样可以换个角度看：在到达第i天时，就获得了在之后任何时候都可以以这一天的售价无限量地买肉的机会。
贪心策略：每遇到一个价格更小的值，一直在这里买，直到遇到下一个更小的值。
1 #include <cstdio> 2 using namespace std; 3 const int MAX_N=100005; 4 int n; 5 int a[MAX_N],p[MAX_N]; 6 7 int main() 8 { 9 scanf("%d",&n); 10 for(int i=0;i<n;i++) 11 scanf("%d%d",&a[i],&p[i]); 12 int minn=p[0]; 13 int ans=minn*a[0]; 14 for(int i=1;i<n;i++) 15 {//每遇到一个价格更小的值，一直在这里买，直到遇到下一个更小的值为止 16 if(p[i]<minn) minn=p[i]; 17 ans+=a[i]*minn; 18 } 19 printf("%d\n", ans); 20 return 0; 21 }
这道题的背景本质上和前两道相同，只是由于容量和供应量都无上限，求最少购买次数没意义，所以增加了一个价格，求总花费的最小值。
贪心策略证明思路：最优值唯一，当没有重复的售价时，最优解也是唯一的。假设存在比贪心策略更小的花费，那么有第 i 天是用比前 i 天的最低价格还要低的价格买到的，而不存在这样的价格，所以不存在更小的花费。
如果容量和供应量都有上限，问题会更复杂，也许贪心思想不再适用，待见到了再来更新吧