首页 > 代码库 > POJ: 2413 ——优先队列——结构体cmp函数一级排序
POJ: 2413 ——优先队列——结构体cmp函数一级排序
我要翻译题目！！！
/*
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).
为了去修补油箱，奶牛们需要尽快将货车拉到最近的城镇（不超过1000000个距离单位),并且经过一条又长又曲折的道路。在这条路上，奶牛们所处的具体位置和城镇之间隔着N个加油站。他们可以在那里得到任意数量的燃料（数据会在1-100之间）
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).
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).
丛林对于人类来说是一个危险的地方，对于奶牛们来说更是如此。因此，奶牛们想要经过最少的加油站（在加油站加油也是需要时间的对吧？）。幸运的是，货车油箱是容量很大。现在货车处于具体城镇L单位的距离上，并且此时车上有P单位的燃料。
Determine the minimum number of stops needed to reach the town, or if the cows cannot reach the town at all.
算出他们需要经过的最少加油站，如果不能到达城镇，就输出-1.
*/
有点机器翻译的感觉，不过真的是我翻译的 T ,T
代码已经在POJ上AC了，思路我参考了资料，但是每一行代码都是我经过思考后写下来的。我会在那些要注意的地方写下我的注释。而且代码有两个版本，一个是使用pair<>来对结构体进行排序，一个是用cmp函数来进行排序。我只贴上cmp的那份。
/*
思路：在路程不变的情况下，要让加油的次数最少，就必须每次尽量多得加油。在计划加油站点的时候，如果发现现在的油量无法使他们到达下一站时，就在前面出现过的可加油量最多的加油站进行加油。这样就不会出现在下一站无法到达的情况。于是可以使用优先队列进行运算。
*/
1 #include <cstdio> 2 #include <algorithm> 3 #include <queue> 4 #define max_n 10000+5 5 using namespace std; 6 7 struct dis_fuel{ 8 int dis; 9 int fuel;10 };
/*
cmp(定义两个空指针，const void *a,const void *b)
强制转换两个空指针为dis_fuel型，并指向结构体中的结构成员dis。若a>b,则返回1，若a<b则返回-1，进行升序处理。
*/11 int cmp(const void *a, const void *b){12 return *(dis_fuel *a).dis > *(dis_fuel *b) ? 1 : -1;15 }16 int main()17 {18 //建立优先队列19 priority_queue <int> que;20 21 struct dis_fuel AB[max_n];22 23 int num,A[max_n],B[max_n],L,P;24 scanf("%d",&num);25 26 for(int i = 0;i < num;i++){27 scanf("%d %d",&A[i],&B[i]);28 }29 scanf("%d %d",&L,&P);30 31 for(int i = 0;i < num;i++){32 AB[i].dis = L - A[i]; 33 AB[i].fuel = B[i];34 }
/*
用qsort进行对结构体进行排序。格式为 qsort(结构数组名，数组的个数，数组元素的内存所占空间，函数名）；
*/35 qsort(AB,num,sizeof(AB[0]),cmp);36 37 AB[num].dis = L;38 AB[num].fuel = 0;39 num++;40 41 int tank = P,pos = 0,ans = 0,dis_;42 /*
在for循环里面对每一个每个currently ponit 进行遍历。如果当前的油量不能保持他走到下一站，则停下来进行加油。此时的油量是前面出现加油站提供的油量的最大 值。如果能，则继续走，并把每个加油站能提供的油量放进优先队列里面。
*/
43 for(int i = 0;i < num;i++){44 dis_ = AB[i].dis - pos;45 46 while(dis_ > tank){47 if(que.empty()){48 printf("-1\n");49 return 0;50 }51 tank += que.top();52 que.pop();53 ans++; 54 }55 56 tank -= dis_;57 pos = AB[i].dis;58 que.push(AB[i].fuel);59 }60 61 printf("%d\n",ans);62 63 return 0;64 65 }
POJ: 2413 ——优先队列——结构体cmp函数一级排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。