三道类似的简单贪心
这几天遇到三道相似的贪心问题。
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(" "); 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 "); 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 "); 45 else printf("%d ",cnt); 46 return 0; 47 }